suppressPackageStartupMessages({
library(ArchR)
library(tidyverse)
library(SingleCellExperiment)
library(zellkonverter)
library(dtwclust)
})
proj <- loadArchRProject("11_added_Ricards_peaks", showLogo = FALSE)
## Successfully loaded ArchRProject!
proj <- addPeak2GeneLinks(ArchRProj = proj,
reducedDims = "atac_LSI_100000",
useMatrix = "GeneExpressionMatrix",
maxDist = 250000,
verbose = TRUE
)
p2g <- getPeak2GeneLinks(
ArchRProj = proj,
corCutOff = -1,
resolution = 1,
FDRCutOff = 1e-04,
varCutOffATAC = .25,
varCutOffRNA = .25,
returnLoops = FALSE
)
P2G-link matrix
# saveRDS(p2g, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/Rmds/peak2gene_links_entire_chromosome_25_04_2022")
#saveRDS(p2g, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/Rmds/new_peak2gene_links_22_04_2022")
p2g <- readRDS("/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/Rmds/new_peak2gene_links_22_04_2022")
Read in the peak accessibility matrix and the gene expression matrix:
# get peak matrix
peaks <- getMatrixFromProject(proj, useMatrix = "PeakMatrix", binarize = FALSE)
## ArchR logging to : ArchRLogs/ArchR-getMatrixFromProject-a2b6775a09fc-Date-2022-04-27_Time-08-41-20.log
## If there is an issue, please report to github with logFile!
## 2022-04-27 08:43:54 : Organizing colData, 2.563 mins elapsed.
## 2022-04-27 08:43:54 : Organizing rowData, 2.564 mins elapsed.
## 2022-04-27 08:43:54 : Organizing rowRanges, 2.565 mins elapsed.
## 2022-04-27 08:43:54 : Organizing Assays (1 of 1), 2.565 mins elapsed.
## 2022-04-27 08:44:08 : Constructing SummarizedExperiment, 2.796 mins elapsed.
## 2022-04-27 08:44:09 : Finished Matrix Creation, 2.805 mins elapsed.
peak_mat <- assays(peaks)[[1]]
# read in gne expresssion matrix
gene_expr <- getMatrixFromProject(proj,
useMatrix = "GeneExpressionMatrix")
## ArchR logging to : ArchRLogs/ArchR-getMatrixFromProject-a2b65f0d12f3-Date-2022-04-27_Time-08-44-09.log
## If there is an issue, please report to github with logFile!
## 2022-04-27 08:47:06 : Organizing colData, 2.954 mins elapsed.
## 2022-04-27 08:47:06 : Organizing rowData, 2.955 mins elapsed.
## 2022-04-27 08:47:06 : Organizing rowRanges, 2.956 mins elapsed.
## 2022-04-27 08:47:06 : Organizing Assays (1 of 1), 2.956 mins elapsed.
## 2022-04-27 08:47:24 : Constructing SummarizedExperiment, 3.263 mins elapsed.
## 2022-04-27 08:47:25 : Finished Matrix Creation, 3.271 mins elapsed.
expr_mat <- assays(gene_expr)[[1]]
rownames(expr_mat) <- rowData(gene_expr)$name
# read in archr gene activity scores
archr_scores <- getMatrixFromProject(proj, useMatrix = "GeneScoreMatrix")
## ArchR logging to : ArchRLogs/ArchR-getMatrixFromProject-a2b6274ca96e-Date-2022-04-27_Time-08-47-25.log
## If there is an issue, please report to github with logFile!
## 2022-04-27 08:49:43 : Organizing colData, 2.306 mins elapsed.
## 2022-04-27 08:49:43 : Organizing rowData, 2.307 mins elapsed.
## 2022-04-27 08:49:43 : Organizing rowRanges, 2.308 mins elapsed.
## 2022-04-27 08:49:43 : Organizing Assays (1 of 1), 2.308 mins elapsed.
## 2022-04-27 08:49:56 : Constructing SummarizedExperiment, 2.526 mins elapsed.
## 2022-04-27 08:49:57 : Finished Matrix Creation, 2.535 mins elapsed.
cp_names <- colnames(colData(archr_scores))
cp_names[20] <- "celltypes"
colnames(colData(archr_scores)) <- cp_names
archr_scores_mat <- assays(archr_scores)[[1]]
rownames(archr_scores_mat) <- rowData(archr_scores)$name
We will only use peaks linked to highly variable genes to compute gene activity scores.
hvg_list <- read.table("jupyter_notebooks/hvg_list", sep = ",")$x
# get RNA index of hvg
meta_rna <- rowData(gene_expr) %>% as.data.frame() %>% mutate(row_index = seq(nrow(.)))
idx <- (meta_rna %>% filter(name %in% hvg_list))$row_index
expr_sub <- expr_mat[idx, ]
links <- p2g %>% as.data.frame() %>%
filter(Correlation > 0.2) %>%
filter(idxRNA %in% idx)
stopifnot(all(links$Correlation > 0))
Create a p2g link matrix
p2g_mat <- sparseMatrix(i = links$idxRNA,
j = links$idxATAC,
x= links$Correlation,
dims = c(dim(expr_mat)[1],
dim(peak_mat)[1]))
rownames(p2g_mat) <- rowData(gene_expr)$name
rownames(peak_mat) <- seq.int(dim(peak_mat)[1])
colnames(p2g_mat) <- seq.int(dim(peak_mat)[1])
Filter and prepare peak matrix and p2g links matrix:
# remove columns of peaks which are not linked to any peak
p2g_mat_sub <- p2g_mat[, colSums(p2g_mat) != 0]
# use only highly variable genes
p2g_mat_sub <- p2g_mat_sub[hvg_list, ]
# remove any genes which are not linked to any peak
p2g_mat_sub <- p2g_mat_sub[rowSums(p2g_mat_sub) != 0, ]
stopifnot(all(rownames(p2g_mat_sub) %in% hvg_list))
stopifnot(any(is.na(p2g_mat_sub) == FALSE))
# keep only peaks which are linked to genes in the accessibility matrix
peak_mat_sub <- peak_mat[colnames(p2g_mat_sub), ]
stopifnot(rownames(peak_mat_sub) == colnames(p2g_mat_sub))
stopifnot(any(is.na(peak_mat_sub) == FALSE))
stopifnot(dim(peak_mat_sub)[1] == dim(p2g_mat_sub)[2])
expr_mat_sub <- expr_mat[as.vector(rownames(p2g_mat_sub)), ]
Function to compute gene activity scores
gene_activity_scores <- function(peak_mat, p2g_mat) {
#peak_mat_subset <- peak_mat[colnames(p2g_mat), ]
# normalize the p2g matrix by the total number of peaks linked to each gene
p2g_mat <- p2g_mat / rowSums(p2g_mat)
print(paste0("normalized the p2g matrix"))
stopifnot(any(is.na(p2g_mat)) == FALSE)
# Now we can compute a weighted sum of peak2gene correlations for each
# peak and gene
scores <- p2g_mat %*% peak_mat
print(paste0("Computed weightes sum of peaks for each gene and cell"))
# create a dataframe for computing the linear model
linear_model_df <- data.frame(cell = colnames(scores),
total_activity = colSums(scores),
total_sites = colSums(peak_mat))
# compute a linear model
activity_model <- stats::lm(log(total_activity) ~ log(total_sites),
data = linear_model_df)
# extract the fitted model
linear_model_df$fitted_curve <- exp(as.vector(predict(activity_model,
type = "response")))
# compute size factors from fitted model
size_factors <- mean(linear_model_df$fitted_curve) / linear_model_df$fitted_curve
# create diagonal matrix containing the size factors
size_factors_mat <- Matrix::Diagonal(x = size_factors)
#row.names(size_factors_mat) <- linear_model_df$cell
# normalize by library depth size factors
norm_scores <- Matrix::t(size_factors_mat %*% Matrix::t(scores))
print(paste0("Normalized for library size"))
# exponentiate, because RNA counts are log-normally distributed
norm_scores@x <- pmin(1e9, exp(norm_scores@x) - 1)
print(paste0("Exponentiated matrix"))
# free some memory
#rm(peak_mat_subset)
rm(activity_model)
rm(scores)
gc(reset = TRUE)
# scale with total activity scores again
scale_factors <- Matrix::Diagonal(x = 1/Matrix::colSums(norm_scores))
print(paste0("Divided by total activity to get value between zero and one"))
final_scores <- Matrix::t(scale_factors %*% Matrix::t(norm_scores))
return(final_scores)
}
p2g_scores <- gene_activity_scores(peak_mat_sub, p2g_mat_sub)
## [1] "normalized the p2g matrix"
## [1] "Computed weightes sum of peaks for each gene and cell"
## [1] "Normalized for library size"
## [1] "Exponentiated matrix"
## [1] "Divided by total activity to get value between zero and one"
Example of p2g links within 250kb
cp_names <- colnames(colData(gene_expr))
cp_names[20] <- "celltypes"
colnames(colData(gene_expr)) <- cp_names
#rownames(expr_mat) <- rowData(gene_expr)$name
genes <- expr_mat[as.vector(rownames(p2g_scores)), ]
stopifnot(any(rownames(genes) == rownames(p2g_scores)))
# create matrix to store aggregates
expr_agg <- matrix(data = 0,
nrow = dim(genes)[1],
ncol = length(unique(colData(gene_expr)$celltypes)),
dimnames = list(rownames(p2g_scores),
unique(colData(gene_expr)$celltypes)))
# fill matrix
for (celltype in unique(colData(gene_expr)$celltypes)){
barcodes <- rownames(colData(gene_expr) %>%
as.data.frame() %>%
filter(celltypes == celltype))
expr_agg[, celltype] <- rowSums(genes[, barcodes])
}
p2g_score_agg <- matrix(data = 0,
nrow = dim(p2g_scores)[1],
ncol = length(unique(colData(gene_expr)$celltypes)),
dimnames = list(rownames(p2g_scores),
unique(colData(gene_expr)$celltypes)))
for (celltype in unique(colData(gene_expr)$celltypes)){
barcodes <- rownames(colData(gene_expr) %>%
as.data.frame() %>%
filter(celltypes == celltype))
p2g_score_agg[, celltype] <- rowSums(p2g_scores[, barcodes])
}
Correlations between aggregated gene expression and aggregated p2g scores for celltypes.
correlations_250kb = c()
for (i in seq.int(dim(p2g_score_agg)[1])){
rowa <- expr_agg[i, ]
rowa <- rowa - mean(rowa)
rowa <- rowa / sd(rowa)
rowb <- p2g_score_agg[i, ]
rowb <- rowb - mean(rowb)
rowb <- rowb / sd(rowb)
corr_value = mean(rowa * rowb)
correlations_250kb <- c(correlations_250kb, corr_value)
}
names(correlations_250kb) <- rownames(p2g_score_agg)
plot_250kb <- ggplot() + geom_histogram(aes(x = correlations_250kb), bins = 200, fill="#69b3a2") +
labs("gene activity scores computed based on p2g links within 250kb of gene")
plot_250kb

knn cell aggregates from ArchR
rna_knn <- readRDS("11_added_Ricards_peaks/Peak2GeneLinks/seRNA-Group-KNN.rds")
rna_agg_mat <- assays(rna_knn)[[1]]
rownames(rna_agg_mat) <- rowData(rna_knn)$name
cell_agg_list <- metadata(rna_knn)[[1]]
knn_aggregates <- function(matrix, cell_agg_list){
# empty matrix to store aggregates
agg <- matrix(data = 0,
nrow = dim(matrix)[1],
ncol = length(cell_agg_list),
dimnames = list(rownames(matrix), NULL))
for (i in seq.int(length(cell_agg_list))) {
agg[, i] <- rowSums(matrix[, cell_agg_list[[i]]])
}
return(agg)
}
rna_agg <- knn_aggregates(expr_mat_sub, cell_agg_list)
agg_p2g_knn <- knn_aggregates(p2g_scores, cell_agg_list)
archr_knn <- archr_scores_mat[as.vector(rownames(agg_p2g_knn)),]
agg_archr_knn <- knn_aggregates(archr_knn, cell_agg_list)
archr_knn <- rowwise_correlations(rna_agg, agg_archr_knn, "Archr gene activity scores")
p2g_knn <- rowwise_correlations(rna_agg, agg_p2g_knn, "Peak-to-gene links activity scores")
cowplot::plot_grid(archr_knn[[2]], p2g_knn[[2]], ncol = 2)
ggplot() + geom_density_2d_filled(aes(x = p2g_knn[[1]],
y = archr_knn[[1]]), alpha = .5) +
geom_point(aes(x = p2g_knn[[1]], y = archr_knn[[1]])) +
geom_line(aes(x = p2g_knn[[1]], y = p2g_knn[[1]]), col = "red")
theme(legend.position = "None")
Functions
Function to prep peak accessibility matrix, gene expression matrix and p2g-link matrix
prep_peak_p2g <- function(peak_mat, p2g_mat, hvg_list, expr_mat){
#rownames(peak_mat) <- seq.int(dim(peak_mat)[1])
#colnames(p2g_mat) <- seq.int(dim(p2g_mat)[2])
# remove columns of peaks which are not linked to any peak
p2g_mat_sub <- p2g_mat[, colSums(p2g_mat) != 0]
# use only highly variable genes
p2g_mat_sub <- p2g_mat_sub[hvg_list, ]
# remove any genes which are not linked to any peak
p2g_mat_sub <- p2g_mat_sub[rowSums(p2g_mat_sub) != 0, ]
stopifnot(all(rownames(p2g_mat_sub) %in% hvg_list))
stopifnot(any(is.na(p2g_mat_sub) == FALSE))
# keep only peaks which are linked to genes in the accessibility matrix
peak_mat_sub <- peak_mat[colnames(p2g_mat_sub), ]
stopifnot(rownames(peak_mat_sub) == colnames(p2g_mat_sub))
stopifnot(any(is.na(peak_mat_sub) == FALSE))
stopifnot(dim(peak_mat_sub)[1] == dim(p2g_mat_sub)[2])
expr_mat_sub <- expr_mat[as.vector(rownames(p2g_mat_sub)), ]
stopifnot(rownames(expr_mat_sub) == rownames(p2g_mat_sub))
return(list(peak_mat_sub, p2g_mat_sub, expr_mat_sub))
}
Function to create celltype aggregates:
# the data matrix needs to be of dimension features x cells
# the column of the colData of the sce object where celltypes are stored
# needs to be called "celltypes"
create_celltype_aggregates <- function(sce, data_matrix, celltypes) {
#create empty matrix to store aggregates
agg <- matrix(data = 0,
nrow = dim(data_matrix)[1],
ncol = length(celltypes),
dimnames = list(rownames(data_matrix), celltypes))
for (celltype in celltypes) {
barcodes <- rownames(colData(sce) %>%
as.data.frame() %>%
filter(celltypes == celltype))
agg[, celltype] <- rowSums(data_matrix[, barcodes])
}
return(agg)
}
create_celltype_aggregates_p2g_scores <- function(gene_expr_sce, p2g_score_matrix, celltypes) {
#create empty matrix to store aggregates
agg <- matrix(data = 0,
nrow = dim(p2g_score_matrix)[1],
ncol = length(celltypes),
dimnames = list(rownames(p2g_score_matrix), celltypes))
for (celltype in celltypes) {
barcodes <- rownames(colData(gene_expr_sce) %>%
as.data.frame() %>%
filter(celltypes == celltype))
agg[, celltype] <- rowSums(p2g_score_matrix[, barcodes])
}
return(agg)
}
Function to compute row-wise correlations between two matrices:
rowwise_correlations <- function(MatrixA, MatrixB, name) {
intersect_genes <- intersect(rownames(MatrixA), rownames(MatrixB))
MatrixA <- MatrixA[intersect_genes, ]
MatrixB <- MatrixB[intersect_genes, ]
correlations <- c()
for (i in seq.int(dim(MatrixA)[1])) {
rowA <- MatrixA[i, ]
rowA <- rowA - mean(rowA)
if (sd(rowA) != 0) {
rowA <- rowA / sd(rowA)
}
rowB <- MatrixB[i, ]
rowB <- rowB - mean(rowB)
if (sd(rowB) != 0){
rowB <- rowB / sd(rowB)
}
corr_value <- mean(rowA * rowB)
correlations <- c(correlations, corr_value)
}
names(correlations) <- rownames(MatrixA)
plot <- ggplot() + geom_histogram(aes(x = correlations),
bins = 200,
fill="#69b3a2") + labs(title = paste0(name))
return(list(correlations, plot))
}
Correlations with ArchR gene activity scores
archr_scores_sub <- archr_scores_mat[as.vector(rownames(expr_agg)), ]
name <- "ArchR_scores"
archr_scores_agg <- create_celltype_aggregates(archr_scores, archr_scores_sub,
unique(colData(archr_scores)$celltypes))
stopifnot(any(is.na(archr_scores_agg)) == FALSE)
corrs <- rowwise_correlations(expr_agg, archr_scores_agg, name)
archr_corr <- corrs[1]
cowplot::plot_grid(plot_250kb + labs(title = "P2g-links activity scores"), corrs[[2]], ncol = 2)

ggplot() + #geom_density2d_filled(aes(x = correlations_250kb, y = corrs[1])) #+
geom_point(aes(x = correlations_250kb, y = corrs[[1]])) +
labs(x = "Correlation gene expression and p2g activity scores",
y = "Correlation gene expression and ArchR gene activity scores")

# ggplot() + geom_point(aes(x = archr_scores_sub["Hba-a1",], y = p2g_scores["Hba-a1",]))
# ggplot() + geom_point(aes(x = archr_scores_sub["Gata6",], y = p2g_scores["Hba-a1",]))
Distance weights
Function to compute distance-weighted gene activity scores from p2g links
!!!!!! Check again! Because here something is wrong with the way I compute the distance weights! Sometimes I need to use the start coordinate instead of the end coordinate. Try always using the gene start coordinate instead of swapping start and end coordinates in the dataframe. Maybe this is done automaticall when converted to dataframe?
# As input for this function it is best to use only the most highly variable genes
distanc_weighted_gene_activity_scores <- function(p2g_mat_sub, geneModel = "exp(-distance/5000)",
weight = 50000,
peak_mat, links, p2g_original, gene_expr){
atac_granges <- metadata(p2g_original)[[1]]
#rna_granges <- metadata(p2g_original)[[2]]
gene_anno <- rowData(gene_expr)
# create gene annotations with start coordinate of each gene
# subset to contain only genes which are included in our peak2gene matrix
gene_anno <- gene_anno %>% as.data.frame() %>%
mutate(idxRNA = seq(nrow(.))) %>%
filter(name %in% rownames(p2g_mat_sub)) %>%
mutate(strand = ifelse(strand == 1, "+", "-")) %>%
mutate(start_coord = ifelse(strand == "+", start, end)) %>%
rename(gene = name) #%>% GRanges()
# subset atac granges & get middle of each peak
pos_atac_granges <- atac_granges %>%
as.data.frame() %>%
mutate(idxATAC = seq(nrow(.))) %>%
# group_by(seqnames) %>%
# mutate(idx = seq_along(seqnames)) %>%
# ungroup %>%
#tidyr::unite(chr_idx, seqnames, idx, remove = FALSE, sep = "_") %>%
filter(idxATAC %in% colnames(p2g_mat_sub)) %>%
mutate(middle = start + 300) #%>% GRanges()
#TODO: Filter for genes!
stopifnot(length(unique(links$idxATAC)) == dim(pos_atac_granges)[[1]])
stopifnot(length(unique(links$idxRNA)) == dim(gene_anno)[[1]])
#p2g_filt <- p2g_original %>% as.data.frame() %>% filter(gene %in% rownames(p2g_mat))
# combine the three dataframes
p2g_join <- left_join(links, as.data.frame(pos_atac_granges),
by = "idxATAC")
p2g_join <- left_join(p2g_join, as.data.frame(gene_anno),
by = "idxRNA", suffix = c(".atac", ".rna"))
# compute distance and distance weights
p2g_join <- p2g_join %>%
mutate(distance = abs(start_coord - middle)) %>%
mutate(distance_weight = eval(parse(text=geneModel)))
p1 <- p2g_join %>% ggplot() +
geom_histogram(aes(x = distance), bins = 100) +
labs(title = "Distance", x = "distance") +
geom_vline(xintercept = 5000, color = "red")
p2 <- p2g_join %>% ggplot() +
geom_histogram(aes(x = (distance_weight)), bins = 100) +
scale_y_log10() +
labs(title = "Distance Weights", x = "distance weights")
cowplot::plot_grid(p1, p2, ncol = 2)
# create distance weight matrix
p2g_dw <- sparseMatrix(i = p2g_join$idxRNA,
j = p2g_join$idxATAC,
x = p2g_join$distance_weight,
dims = c(dim(assays(gene_expr)[[1]])[1],
dim(peak_mat)[1]),
dimnames = list(rowData(gene_expr)$name ,
seq.int(dim(peak_mat)[1])))
p2g_dw <- p2g_dw[as.vector(rownames(p2g_mat_sub)), colnames(p2g_mat_sub)]
# elementwise matrix multiplication
weighted_p2g_mat <- p2g_mat_sub * p2g_dw
print(paste(length(which(rowSums(weighted_p2g_mat) == 0)), "genes have only zero correlation values, so we will remove them."))
weighted_p2g_mat <- weighted_p2g_mat[rowSums(weighted_p2g_mat) != 0, ]
print(paste0("We are left with ", dim(weighted_p2g_mat)[1], " genes"))
# compute gene activity scores based on distance-weighted peak2gene matrix
weighted_scores <- gene_activity_scores(peak_mat_sub, weighted_p2g_mat)
return(weighted_scores)
}
weighted_scores <- distanc_weighted_gene_activity_scores(p2g_mat_sub, geneModel = "exp(-distance/5000)",
weight = 50000,
peak_mat, links, p2g, gene_expr)
## [1] "0 genes have only zero correlation values, so we will remove them."
## [1] "We are left with 1241 genes"
## [1] "normalized the p2g matrix"
## [1] "Computed weightes sum of peaks for each gene and cell"
## [1] "Normalized for library size"
## [1] "Exponentiated matrix"
## [1] "Divided by total activity to get value between zero and one"
model_list <- c("exp(-abs(distance)/5000)", "exp(-abs(distance)/50000)",
"exp(-abs(distance)/500000)", "exp(-abs(distance)/5000000)")
# read in knn
rna_knn <- readRDS("11_added_Ricards_peaks/Peak2GeneLinks/seRNA-Group-KNN.rds")
cell_agg_list <- metadata(rna_knn)[[1]]
# Function to compute aggregates with knn from ArchR
knn_aggregates <- function(matrix, cell_agg_list){
# empty matrix to store aggregates
agg <- matrix(data = 0,
nrow = dim(matrix)[1],
ncol = length(cell_agg_list),
dimnames = list(rownames(matrix), NULL))
for (i in seq.int(length(cell_agg_list))) {
agg[, i] <- rowSums(matrix[, cell_agg_list[[i]]])
}
return(agg)
}
# aggregate for gene expression, ArchR gene activity scores and simple p2g links
rna_agg <- knn_aggregates(expr_mat_sub, cell_agg_list)
archr_knn <- archr_scores_mat[as.vector(rownames(rna_agg)),]
agg_archr_knn <- knn_aggregates(archr_knn, cell_agg_list)
agg_p2g_knn <- knn_aggregates(p2g_scores, cell_agg_list)
# compute rowwise correlations
archr_knn <- rowwise_correlations(rna_agg, agg_archr_knn, "Archr gene activity scores")
p2g_knn <- rowwise_correlations(rna_agg, agg_p2g_knn, "Peak-to-gene links activity scores")
cowplot::plot_grid(archr_knn[[2]], p2g_knn[[2]], ncol = 2)

# prepare lists to store correlation vectors and correlation histograms
corr_list <- list(archr_knn[[1]], p2g_knn[[1]])
# compute the distance-weighted gene activity scores from p2g links using different
# distance weight models
for (model in model_list){
weighted_scores <- distanc_weighted_gene_activity_scores(p2g_mat_sub,
geneModel = model,
weight = 50000,
peak_mat = peak_mat,
links = links,
p2g_original = p2g,
gene_expr = gene_expr)
agg_dist <- knn_aggregates(weighted_scores, cell_agg_list)
dist_knn <- rowwise_correlations(rna_agg, agg_dist, name = paste0("P2g activity scores, distance weihted, model = ", model))
stopifnot(any(is.na(dist_knn)) == FALSE)
corr_list <- append(corr_list, dist_knn[[1]])
print(dist_knn[[2]])
#corr_plots_list <- append(corr_plots_list, dist_knn[[2]])
plot <- ggplot() + #geom_density_2d_filled(aes(x = corr_list[[i]],
# y = corr_list[[1]]), alpha = .5) +
geom_point(aes(x = dist_knn[[1]], y = corr_list[[1]])) +
geom_line(aes(x = dist_knn[[1]], y = dist_knn[[1]]), col = "red") +
theme(legend.position = "None") +
labs(x = "Correlation between gene expression and p2g activity scores",
title = paste0(model),
y = "Correlation between gene expression and ArchR gene activity scores")
print(plot)
}
## [1] "0 genes have only zero correlation values, so we will remove them."
## [1] "We are left with 1241 genes"
## [1] "normalized the p2g matrix"
## [1] "Computed weightes sum of peaks for each gene and cell"
## [1] "Normalized for library size"
## [1] "Exponentiated matrix"
## [1] "Divided by total activity to get value between zero and one"


## [1] "0 genes have only zero correlation values, so we will remove them."
## [1] "We are left with 1241 genes"
## [1] "normalized the p2g matrix"
## [1] "Computed weightes sum of peaks for each gene and cell"
## [1] "Normalized for library size"
## [1] "Exponentiated matrix"
## [1] "Divided by total activity to get value between zero and one"

## Warning: Transformation introduced infinite values in continuous y-axis
## Warning: Removed 10 rows containing missing values (geom_bar).

## [1] "0 genes have only zero correlation values, so we will remove them."
## [1] "We are left with 1241 genes"
## [1] "normalized the p2g matrix"
## [1] "Computed weightes sum of peaks for each gene and cell"
## [1] "Normalized for library size"
## [1] "Exponentiated matrix"
## [1] "Divided by total activity to get value between zero and one"

## Warning: Transformation introduced infinite values in continuous y-axis
## Warning: Removed 29 rows containing missing values (geom_bar).

## [1] "0 genes have only zero correlation values, so we will remove them."
## [1] "We are left with 1241 genes"
## [1] "normalized the p2g matrix"
## [1] "Computed weightes sum of peaks for each gene and cell"
## [1] "Normalized for library size"
## [1] "Exponentiated matrix"
## [1] "Divided by total activity to get value between zero and one"


# cowplot::plot_grid(corr_plots_list, ncol = 2)
# do.call(what = cowplot::plot_grid, args = append(corr_plots_list),
# list(ncol = 2))#, nrow = length(corr_plots_list)/2)))
#
# plot_list <- list()
# for (i in length(corr_list)){
# rna_archr_corr <- corr_list[[1]]
# if (i != 1){
# #corr_vector <- corr_list[[1]]
# plot <- ggplot() + geom_density_2d_filled(aes(x = corr_list[[i]],
# y = corr_list[[1]]), alpha = .5) +
# geom_point(aes(x = corr_list[[i]], y = corr_list[[1]])) +
# geom_line(aes(x = corr_list[[i]], y = corr_list[[i]]), col = "red") +
# theme(legend.position = "None")
# #plot_list <- append(plot_list, plot)
#
# }
# }
#
# do.call(what = cowplot::plot_grid, args = append(plot_list))
Gene window, no distance weights
# As input for this function it is best to use only the most highly variable genes
compute_gene_window_score <- function(p2g_mat_sub, weight = 50000, peak_mat, links, p2g_original, gene_expr){
atac_granges <- metadata(p2g_original)[[1]]
#rna_granges <- metadata(p2g_original)[[2]]
gene_anno <- rowData(gene_expr)
# create gene annotations with start coordinate of each gene
# subset to contain only genes which are included in our peak2gene matrix
gene_anno <- gene_anno %>% as.data.frame() %>%
mutate(idxRNA = seq(nrow(.))) %>%
filter(name %in% rownames(p2g_mat_sub)) %>%
mutate(strand = ifelse(strand == 1, "+", "-")) %>%
mutate(start_coord = ifelse(strand == "+", start, end)) %>%
rename(gene = name) #%>% GRanges()
#geneRegions <- gene_anno %>% GRanges()
gene_regions <- resize(gene_anno %>% GRanges(), width = 1)
extendedGeneRegion <- (suppressWarnings(extendGR(gene_regions,
upstream = 100000,
downstream = 100000)))
# subset atac granges & get middle of each peak
pos_atac_granges <- atac_granges %>%
as.data.frame() %>%
mutate(idxATAC = seq(nrow(.))) %>%
# group_by(seqnames) %>%
# mutate(idx = seq_along(seqnames)) %>%
# ungroup %>%
#tidyr::unite(chr_idx, seqnames, idx, remove = FALSE, sep = "_") %>%
filter(idxATAC %in% colnames(p2g_mat_sub)) %>%
mutate(middle = start + 300) #%>% GRanges()
#TODO: Filter for genes!
stopifnot(length(unique(links$idxATAC)) == dim(pos_atac_granges)[[1]])
stopifnot(length(unique(links$idxRNA)) == dim(gene_anno)[[1]])
#p2g_filt <- p2g_original %>% as.data.frame() %>% filter(gene %in% rownames(p2g_mat))
# find overlapping peaks and gene window in chromosome-aware fashion
tmp <- suppressWarnings(findOverlaps(extendedGeneRegion, pos_atac_granges %>% GRanges()))
print(paste0("Out of ", subjectLength(tmp), " peaks only ",
length(unique(subjectHits(tmp))), " peaks are found within gene window of 200kb."))
### some plots
print(tmp %>% as.data.frame() %>%
group_by(queryHits) %>% # gene region
summarize(n = n()) %>% # get number of peaks overlapping with a gene region
ggplot() + geom_histogram(aes(x = n), bins = 100, fill="#69b3a2") +
labs(title = "number of peaks per gene region of size +/- 100kb from TSS",
x = "number of peaks within window",))
# combine the three dataframes
p2g_join <- left_join(links, as.data.frame(pos_atac_granges),
by = "idxATAC")
p2g_join <- left_join(p2g_join, as.data.frame(gene_anno),
by = "idxRNA", suffix = c(".atac", ".rna"))
# compute distance and distance weights
p2g_join <- p2g_join %>%
mutate(distance = abs(start_coord - middle))# %>%
# mutate(distance_weight = eval(parse(text=geneModel)))
p1 <- p2g_join %>% ggplot() +
geom_histogram(aes(x = distance), bins = 100) +
labs(title = "Distance", x = "distance") +
geom_vline(xintercept = 100000, color = "red")
# p2 <- p2g_join %>% ggplot() +
# geom_histogram(aes(x = (distance_weight)), bins = 100) +
# scale_y_log10() +
# labs(title = "Distance Weights", x = "distance weights")
print(cowplot::plot_grid(p1))#), ncol = 2))
# create a dataframe of all peaks which overlap their corresponding gene window
peaks_in_gene_window <- data.frame(gene = gene_regions[queryHits(tmp)]$gene,
peak = (pos_atac_granges %>% GRanges())[subjectHits(tmp)]$idxATAC) %>%
unite(peak_gene_window, gene, peak, sep = "#", remove = FALSE)
# filter the p2g link dataframe for only peaks which are within a gene window
corr_window <- p2g_join %>%
unite(peak_gene_window, gene, idxATAC, sep = "#", remove = FALSE) %>%
filter(peak_gene_window %in% peaks_in_gene_window$peak_gene_window)
### PLOTS
p1 <- corr_window %>%
ggplot() +
geom_histogram(aes(x = Correlation), bins = 200, fill = "#69b3a2") +
labs(title = "Correlation values of peaks found within gene windows")
p2 <- corr_window %>%
ggplot() +
geom_histogram(aes(x = distance), bins = 200, fill = "#69b3a2") +
labs(title = "Distance between peaks and genes found within gene windows and TSS")
p3 <- corr_window %>%
mutate(bin = cut_width(distance, width=10000, boundary=0)) %>%
ggplot() +
geom_boxplot(aes(x = bin, y = Correlation), fill = "#69b3a2") +
labs(title = "Distance and Correlation within gene window, 1000bp bins",
x = "Distance (1000bp bins)")
print(cowplot::plot_grid(p1, p2, p3, ncol = 2))
p1 <- ggplot() +
geom_histogram(aes(x = rowSums(p2g_mat_sub > 0)), bins = 200, fill = "#69b3a2") +
scale_y_log10() +
labs(title = "Number of peaks correlated with each gene",
x = "number of peaks", y = "log10(count)")
p2 <- ggplot() +
geom_histogram(aes(x = colSums(p2g_mat_sub > 0)), bins = 70, fill = "#69b3a2") +
scale_y_log10() +
labs(title = "Number of genes correlated with each peak",
y = "log10(count)", x = "number of genes")
p3 <- ggplot() +
geom_histogram(aes(x = rowSums(p2g_mat_sub > 0)), bins = 200, fill = "#69b3a2") +
labs(title = "Number of peaks correlated with each gene",
x = "number of peaks", y = "count")
p4 <- ggplot() +
geom_histogram(aes(x = colSums(p2g_mat_sub > 0)), bins = 70, fill = "#69b3a2") +
labs(title = "Number of genes correlated with each peak",
y = "count", x = "number of genes")
print(cowplot::plot_grid(p1, p2, p3, p4, ncol = 2))
peak_middle_region <- pos_atac_granges %>% GRanges()
# add the half width to the start of each peak
start(peak_middle_region) = start(peak_middle_region) +
floor(width(peak_middle_region) / 2)
# resize the ranges so we only have the middle of each peak
peak_middle_region <- resize(peak_middle_region, 1, "start")
# compute the distances between peak middle and gene TSS of all peaks which
# overlap with a gene window
distance <- distance(ranges(gene_regions)[queryHits(tmp)],
ranges(resize(peak_middle_region, width = 1))[subjectHits(tmp)])
### PLOT
# p1 <- ggplot() + geom_histogram(aes(x = distance), bins = 200) +
# scale_y_log10() +
# labs(title = "Distance between peak middle and gene TSS within a gene window",
# y = "log10(count)") +
# geom_vline(xintercept = 100000, color = "red")
isMinus <- BiocGenerics::which(strand(gene_regions) == "-")
# subtract the gene start coordinate from the tile start coordinate -> relative distances
signDist <- sign(start(peak_middle_region)[subjectHits(tmp)] -
start(resize(gene_regions,1,"start"))[queryHits(tmp)])
# convert the direction of distance for all distances corresponding to the negative strand
signDist[isMinus] <- signDist[isMinus] * -1
distance <- distance * signDist
#### PLOT
p2 <- ggplot() + geom_histogram(aes(x = distance), bins = 500) +
scale_y_log10() +
labs(title = "Distribution of relative distances between genes and peaks within a gene region",
x = "relative distance to TSS", y = "log10(count)") +
geom_vline(xintercept = c(100000, -100000), color = "red")
print(p2)
#cowplot::plot_grid(p1, p2, ncol = 1)
corr_window$ColIndex <- match(corr_window$idxATAC, unique(corr_window$idxATAC))
corr_window$RowIndex <- match(corr_window$gene, unique(corr_window$gene))
p2g_links_gene_window <- Matrix::sparseMatrix(
i = corr_window$idxRNA,
j = corr_window$idxATAC,
x = corr_window$Correlation,
dims = c(nrow(expr_mat), nrow(peak_mat)),
dimnames = list(rownames(expr_mat),rownames(peak_mat))
)
print(paste0("The peak-to-gene links matrix, restricted to a +/- 100kb window around the TSS has dimensions ", split(dim(p2g_links_gene_window), 1)))
print(paste0("The maximum value is: ", max(p2g_links_gene_window), ", the minum value is: ", min(p2g_links_gene_window) ))
p2g_links_gene_window <- p2g_links_gene_window[rowSums(p2g_links_gene_window) != 0, ]
p2g_links_gene_window <- p2g_links_gene_window[, colSums(p2g_links_gene_window) != 0]
print(paste0("After removing any rows and columsn which do not contain any links we are left with ", nrow(p2g_links_gene_window), " genes and ", ncol(p2g_links_gene_window), " peaks."))
# Compute gene activity scores
gene_window_scores <- gene_activity_scores(peak_mat_sub[colnames(p2g_links_gene_window), ], p2g_links_gene_window)
dim(gene_window_scores)
# # create distance weight matrix
# p2g_dw <- sparseMatrix(i = p2g_join$idxRNA,
# j = p2g_join$idxATAC,
# x = p2g_join$distance_weight,
# dims = c(dim(assays(gene_expr)[[1]])[1],
# dim(peak_mat)[1]),
# dimnames = list(rowData(gene_expr)$name ,
# seq.int(dim(peak_mat)[1])))
#
#
# p2g_dw <- p2g_dw[as.vector(rownames(p2g_mat_sub)), colnames(p2g_mat_sub)]
#
# # elementwise matrix multiplication
# weighted_p2g_mat <- p2g_mat_sub * p2g_dw
#
# print(paste(length(which(rowSums(weighted_p2g_mat) == 0)), "genes have only zero correlation values, so we will remove them."))
# weighted_p2g_mat <- weighted_p2g_mat[rowSums(weighted_p2g_mat) != 0, ]
# print(paste0("We are left with ", dim(weighted_p2g_mat)[1], " genes"))
#
# # compute gene activity scores based on distance-weighted peak2gene matrix
# weighted_scores <- gene_activity_scores(peak_mat_sub, weighted_p2g_mat)
return(gene_window_scores)
}
gene_window_scores <- compute_gene_window_score(
p2g_mat_sub = p2g_mat_sub,
weight = 50000,
peak_mat = peak_mat,
links = links,
p2g_original = p2g,
gene_expr = gene_expr)
## [1] "Out of 12778 peaks only 7122 peaks are found within gene window of 200kb."


## Warning: Transformation introduced infinite values in continuous y-axis
## Warning: Removed 148 rows containing missing values (geom_bar).
## Warning: Transformation introduced infinite values in continuous y-axis
## Warning: Removed 64 rows containing missing values (geom_bar).



## [1] "The peak-to-gene links matrix, restricted to a +/- 100kb window around the TSS has dimensions c(16701, 180499)"
## [1] "The maximum value is: 0.939676699453905, the minum value is: 0"
## [1] "After removing any rows and columsn which do not contain any links we are left with 1105 genes and 5902 peaks."
## [1] "normalized the p2g matrix"
## [1] "Computed weightes sum of peaks for each gene and cell"
## [1] "Normalized for library size"
## [1] "Exponentiated matrix"
## [1] "Divided by total activity to get value between zero and one"
weighted_scores_agg <- knn_aggregates(gene_window_scores, cell_agg_list)
weighted_knn_corr <- rowwise_correlations(rna_agg, weighted_scores_agg,
"P2g links within gene window")
weighted_knn_corr[[2]]

ggplot() + geom_density_2d_filled(aes(x = weighted_knn_corr[[1]],
y = archr_knn[[1]][names(weighted_knn_corr[[1]])]), alpha = .5) +
geom_point(aes(x = weighted_knn_corr[[1]], y = archr_knn[[1]][names(weighted_knn_corr[[1]])])) +
geom_line(aes(x = weighted_knn_corr[[1]], y = weighted_knn_corr[[1]]), col = "red") +
theme(legend.position = "None") +
labs(x = "Correlation between gene expression and p2g activity scores",
title = "Peak-to-gene links are restricted to a gene window of +/- 100kb around TSS",
y = "Correlation between gene expression and ArchR gene activity scores")

Effect of using different distance decay rates
How does the distance weight distribution change with different decay rates?
Here, we use the formula \(e^{\frac{-abs(distance)}{c}}\) with differen decay rates \(c \in \{5000, 50000, 500000, 5000000\}\). Additionally, we use only peaks which overlap with a +/- 1000kb window from the TSS.
model_list <- c("exp(-abs(distance)/5000)", "exp(-abs(distance)/50000)",
"exp(-abs(distance)/500000)", "exp(-abs(distance)/5000000)")
atac_granges <- metadata(p2g)[[1]]
#rna_granges <- metadata(p2g_original)[[2]]
gene_anno <- rowData(gene_expr)
# create gene annotations with start coordinate of each gene
# subset to contain only genes which are included in our peak2gene matrix
gene_anno <- gene_anno %>% as.data.frame() %>%
mutate(idxRNA = seq(nrow(.))) %>%
filter(name %in% rownames(p2g_mat_sub)) %>%
mutate(strand = ifelse(strand == 1, "+", "-")) %>%
mutate(start_coord = ifelse(strand == "+", start, end)) %>%
rename(gene = name) #%>% GRanges()
#geneRegions <- gene_anno %>% GRanges()
gene_regions <- resize(gene_anno %>% GRanges(), width = 1)
extendedGeneRegion <- (suppressWarnings(extendGR(gene_regions,
upstream = 100000,
downstream = 100000)))
# subset atac granges & get middle of each peak
pos_atac_granges <- atac_granges %>%
as.data.frame() %>%
mutate(idxATAC = seq(nrow(.))) %>%
# group_by(seqnames) %>%
# mutate(idx = seq_along(seqnames)) %>%
# ungroup %>%
#tidyr::unite(chr_idx, seqnames, idx, remove = FALSE, sep = "_") %>%
filter(idxATAC %in% colnames(p2g_mat_sub)) %>%
mutate(middle = start + 300) #%>% GRanges()
#TODO: Filter for genes!
stopifnot(length(unique(links$idxATAC)) == dim(pos_atac_granges)[[1]])
stopifnot(length(unique(links$idxRNA)) == dim(gene_anno)[[1]])
#p2g_filt <- p2g_original %>% as.data.frame() %>% filter(gene %in% rownames(p2g_mat))
# find overlapping peaks and gene window in chromosome-aware fashion
tmp <- suppressWarnings(findOverlaps(extendedGeneRegion, pos_atac_granges %>% GRanges()))
print(paste0("Out of ", subjectLength(tmp), " peaks only ",
length(unique(subjectHits(tmp))), " peaks are found within gene window of 200kb."))
## [1] "Out of 12778 peaks only 7122 peaks are found within gene window of 200kb."
### some plots
print(tmp %>% as.data.frame() %>%
group_by(queryHits) %>% # gene region
summarize(n = n()) %>% # get number of peaks overlapping with a gene region
ggplot() + geom_histogram(aes(x = n), bins = 100, fill="#69b3a2") +
labs(title = "number of peaks per gene region of size +/- 100kb from TSS",
x = "number of peaks within window"))

# combine the three dataframes
p2g_join <- left_join(links, as.data.frame(pos_atac_granges),
by = "idxATAC")
p2g_join <- left_join(p2g_join, as.data.frame(gene_anno),
by = "idxRNA", suffix = c(".atac", ".rna"))
for (model in model_list){
# compute distance and distance weights
p2g_join <- p2g_join %>%
mutate(distance = abs(start_coord - middle)) %>%
mutate(distance_weight = eval(parse(text=model)))
p1 <- p2g_join %>% ggplot() +
geom_histogram(aes(x = distance), bins = 200, fill="#69b3a2") +
labs(title = "Distance between peaks and genes", x = "distance") +
geom_vline(xintercept = 5000, color = "red") +
geom_vline(xintercept = 250000, color = "orange")
p2 <- p2g_join %>% ggplot() +
geom_histogram(aes(x = (distance_weight)), bins = 200, fill="#69b3a2") +
scale_y_log10() +
labs(title = paste0("Distance Weights computed using ", model),
x = "distance weights", y = "log10(counts)")
print(cowplot::plot_grid(p1, p2, ncol = 2))
}
## Warning: Transformation introduced infinite values in continuous y-axis
## Warning: Removed 2 rows containing missing values (geom_bar).

## Warning: Transformation introduced infinite values in continuous y-axis
## Warning: Removed 38 rows containing missing values (geom_bar).

## Warning: Transformation introduced infinite values in continuous y-axis
## Warning: Removed 83 rows containing missing values (geom_bar).


# Relationship between distance and correlation value
# p3 <- p2g_join %>% ggplot() +
# geom_point(aes(x = Correlation, y = distance)) +
# labs(title = "Distance vs. correlation between peaks and genes",
# x = "Correlation between peak and gene",
# y = "Distance between peak and gene")
#
#
# p4 <- p2g_join %>% ggplot() +
# geom_point(aes(x = Correlation, y = distance_weight)) +
# labs(title = "Distance vs. correlation between peaks and genes",
# x = "Correlation between peak and gene",
# y = "Distance weights between peak and gene")
#cowplot::plot_grid(p1, p2, ncol = 1)
Relationship between distance and correlation values
# Olot relationship between distance and correlation as density plots
p1 <- p2g_join %>% ggplot() +
geom_density_2d_filled(aes(x = Correlation, y = distance)) +
theme(legend.position = "None") +
labs(title = "Relationship between distance and correlation")
p2 <- p2g_join %>%
filter(Correlation > 0.3) %>%
ggplot() +
geom_density_2d_filled(aes(x = Correlation, y = distance)) +
theme(legend.position = "None") +
labs(title = "Relationship between distance and correlation")
p3 <- p2g_join %>%
filter(Correlation > 0.6) %>%
ggplot() +
geom_density_2d_filled(aes(x = Correlation, y = distance)) +
theme(legend.position = "None") +
labs(title = "Relationship between distance and correlation")
cowplot::plot_grid(p1, p2, p3, ncol = 2)

p2g_join %>%
mutate(bin=cut_width(distance, width=10000, boundary=0)) %>%
filter(distance < 250000) %>%
ggplot() +
geom_boxplot(aes(x = bin, y = Correlation), fill="#69b3a2") +
#geom_vline(xintercept = 250000, color = "red") +
labs(title = "Relationship between distance and correlation of p2g links, 100kb bins",
x = "Distance between peaks and genes within 250kb", y = "Correlation") +
theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust=1))

p1 <- p2g_join %>%
mutate(bin=cut_width(distance, width=100000, boundary=0)) %>%
filter(distance < 10000000 & Correlation > 0.5) %>%
ggplot() +
geom_boxplot(aes(x = bin, y = Correlation), fill="#69b3a2") +
labs(title = "Relationship between distance and correlation of p2g links, 100kb bins",
x = "Distance < 1e^7 bp", y = "Correlation > 0.5") +
theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust=1))
p2 <- p2g_join %>%
mutate(bin=cut_width(distance, width=100000, boundary=0)) %>%
filter(distance < 10000000 & Correlation > 0.8) %>%
ggplot() +
geom_boxplot(aes(x = bin, y = Correlation), fill="#69b3a2") +
labs(title = "Relationship between distance and correlation of p2g links, 100kb bins",
x = "Distance < 1e^7 bp", y = "Correlation > 0.8") +
theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust=1))
p3 <- p2g_join %>%
mutate(bin=cut_width(distance, width=100000, boundary=0)) %>%
filter(distance < 10000000 & Correlation < 0.5) %>%
ggplot() +
geom_boxplot(aes(x = bin, y = Correlation), fill="#69b3a2") +
labs(title = "Relationship between distance and correlation of p2g links, 100kb bins",
x = "Distance < 1e^7 bp", y = "Correlation < 0.5") + theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust=1))
p4 <- p2g_join %>%
mutate(bin=cut_width(distance, width=1000, boundary=0)) %>%
filter(distance < 100000 & Correlation > 0.5) %>%
ggplot() +
geom_boxplot(aes(x = bin, y = Correlation), fill="#69b3a2") +
labs(title = "Relationship between distance and correlation of p2g links, 1kb bins",
x = "Distance < 100kb", y = "Correlation > 0.5") + theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust=1))
cowplot::plot_grid(p1, p2, p3, p4, ncol = 2)

Try distance weights
rna_knn <- readRDS("11_added_Ricards_peaks/Peak2GeneLinks/seRNA-Group-KNN.rds")
#rna_agg_mat <- assays(rna_knn)[[1]]
#rownames(rna_agg_mat) <- rowData(rna_knn)$name
cell_agg_list <- metadata(rna_knn)[[1]]
knn_aggregates <- function(matrix, cell_agg_list){
# empty matrix to store aggregates
agg <- matrix(data = 0,
nrow = dim(matrix)[1],
ncol = length(cell_agg_list),
dimnames = list(rownames(matrix), NULL))
for (i in seq.int(length(cell_agg_list))) {
agg[, i] <- rowSums(matrix[, cell_agg_list[[i]]])
}
return(agg)
}
rna_agg <- knn_aggregates(expr_mat_sub, cell_agg_list)
archr_knn <- archr_scores_mat[as.vector(rownames(agg_p2g_knn)),]
agg_archr_knn <- knn_aggregates(archr_knn, cell_agg_list)
agg_p2g_knn <- knn_aggregates(p2g_scores, cell_agg_list)
agg_dist <- knn_aggregates(weighted_scores, cell_agg_list)
archr_knn <- rowwise_correlations(rna_agg, agg_archr_knn, "Archr gene activity scores")
p2g_knn <- rowwise_correlations(rna_agg, agg_p2g_knn, "Peak-to-gene links activity scores")
dist_knn <- rowwise_correlations(rna_agg, agg_dist, "Peak-to_gene links activity scores weighted by distance")
cowplot::plot_grid(archr_knn[[2]], p2g_knn[[2]], dist_knn[[2]], ncol = 2)

p1 <- ggplot() + geom_density_2d_filled(aes(x = p2g_knn[[1]],
y = archr_knn[[1]]), alpha = .5) +
geom_point(aes(x = p2g_knn[[1]], y = archr_knn[[1]])) +
geom_line(aes(x = p2g_knn[[1]], y = p2g_knn[[1]]), col = "red") +
theme(legend.position = "None")
p2 <- ggplot() + geom_density_2d_filled(aes(x = dist_knn[[1]],
y = archr_knn[[1]]), alpha = .5) +
geom_point(aes(x = dist_knn[[1]], y = archr_knn[[1]])) +
geom_line(aes(x = dist_knn[[1]], y = dist_knn[[1]]), col = "red") +
theme(legend.position = "None")
cowplot::plot_grid(p1, p2, ncol = 2)

Example restricting links to Gene window
Lets check whether the results we got previously also yield high correlations. In this case, using all p2g links across the entire chromsome, we computed gene activity scores, but restricting links to within a gene window of +/- 100kb.
test <- readH5AD("jupyter_notebooks/p2g_gene_activity_scores/gene_window_scoresgene_window_scores")
## ℹ Using stored X_name value 'gene_window_scores'
p2g_scores <- assays(test)[[1]]
# cp_names <- colnames(colData(gene_expr))
# cp_names[20] <- "celltypes"
# colnames(colData(gene_expr)) <- cp_names
rownames(expr_mat) <- rowData(gene_expr)$name
genes <- expr_mat[as.vector(rownames(p2g_scores)), ]
stopifnot(any(rownames(genes) == rownames(p2g_scores)))
# create matrix to store aggregates
expr_agg <- matrix(data = 0,
nrow = dim(genes)[1],
ncol = length(unique(colData(gene_expr)$celltypes)),
dimnames = list(rownames(p2g_scores),
unique(colData(gene_expr)$celltypes)))
# fill matrix
for (celltype in unique(colData(gene_expr)$celltypes)){
barcodes <- rownames(colData(gene_expr) %>%
as.data.frame() %>%
filter(celltypes == celltype))
expr_agg[, celltype] <- rowSums(genes[, barcodes])
}
p2g_score_agg <- matrix(data = 0,
nrow = dim(p2g_scores)[1],
ncol = length(unique(colData(gene_expr)$celltypes)),
dimnames = list(rownames(p2g_scores),
unique(colData(gene_expr)$celltypes)))
for (celltype in unique(colData(gene_expr)$celltypes)){
barcodes <- rownames(colData(gene_expr) %>%
as.data.frame() %>%
filter(celltypes == celltype))
p2g_score_agg[, celltype] <- rowSums(p2g_scores[, barcodes])
}
Correlations between aggregated gene expression and aggregated p2g scores:
correlations_gene_window = c()
for (i in seq.int(dim(p2g_score_agg)[1])){
rowa <- expr_agg[i, ]
rowa <- rowa - mean(rowa)
rowa <- rowa / sd(rowa)
rowb <- p2g_score_agg[i, ]
rowb <- rowb - mean(rowb)
rowb <- rowb / sd(rowb)
corr_value = mean(rowa * rowb)
correlations_gene_window <- c(correlations_gene_window, corr_value)
}
names(correlations_gene_window) <- rownames(p2g_score_agg)
ggplot() + geom_histogram(aes(x = correlations_gene_window), bins = 200) +
labs(title = "Gene activity scores computed based on p2g links on entire chromosome,
but restricted to +/-100kb gene window around TSS")

correlations_gene_window_sub <- correlations_gene_window[names(correlations_250kb)]
ggplot() + #geom_density2d_filled(aes(x = correlations_250kb, y = corrs[1])) #+
geom_point(aes(x = correlations_250kb, y = correlations_gene_window_sub))
## Warning: Removed 213 rows containing missing values (geom_point).

Adapted Archr Gene Activity Score function
ArchR Gene Activity Scores using gene body
ArchR Gene Activity Scores using gene body
#saveArchRProject(proj, "12_Copy2/")
proj <- loadArchRProject("12_Copy2/")
proj <- addKathiGeneScoreMatrix(
proj,
genes = getGenes(proj),
peaks = getPeakSet(proj),
geneModel = "exp(-abs(x)/5000) + exp(-1)",
matrixName = "GeneScoreMatrix",
extendUpstream = c(1000, 100000),
extendDownstream = c(1000, 100000),
#geneUpstream = 5000, #New Param
#geneDownstream = 0, #New Param
useGeneBoundaries = TRUE,
useTSS = FALSE, #New Param
extendTSS = FALSE,
tileSize = 500,
ceiling = 4,
geneScaleFactor = 5, #New Param
scaleTo = 10000,
excludeChr = c("chrY", "chrM"),
blacklist = getBlacklist(proj),
threads = 1,
parallelParam = NULL,
subThreading = TRUE,
force = TRUE,
logFile = createLogFile(".addKathiGeneScoreMat"))
scores <- getMatrixFromProject(proj, useMatrix = "GeneScoreMatrix")
scores_mat <- assays(scores)[[1]]
rownames(scores_mat) <- rowData(scores)$name
# sce <- SingleCellExperiment(list(scores=scores_mat),
# rowData = as.data.frame(rowData(scores)),
# colData = as.data.frame(colnames(scores_mat)))
#
# writeH5AD(sce, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/jupyter_notebooks/p2g_gene_activity_scores/archr_scores_gene_body_peak_based", X_name = "scores")
Correlating gene expression with activity scores:
archr_gene_body_agg <- knn_aggregates(scores_mat, cell_agg_list)
gene_body_knn <- rowwise_correlations(rna_agg, archr_gene_body_agg, "ArchR gene activity scores based on peak matrix, using gene body")
cowplot::plot_grid(archr_knn[[2]], gene_body_knn[[2]], ncol = 2)
p1 <- ggplot() + geom_density_2d_filled(aes(x = gene_body_knn[[1]],
y = archr_knn[[1]]), alpha = .5) +
geom_point(aes(x = gene_body_knn[[1]], y = archr_knn[[1]])) +
geom_line(aes(x = gene_body_knn[[1]], y = gene_body_knn[[1]]), col = "red") +
theme(legend.position = "None")
ArchR Gene Activity Scores using TSS, no gene body
ArchR Gene Activity Scores using TSS, no gene body
#saveArchRProject(proj, "12_Copy1/")
proj <- loadArchRProject("12_")
proj <- addGeneScoreMatrix(
proj,
genes = getGenes(proj),
geneModel = "exp(-abs(x)/5000)",
matrixName = "GeneScoreMatrix",
extendUpstream = c(1000, 100000),
extendDownstream = c(1000, 100000),
#geneUpstream = 5000, #New Param
#geneDownstream = 0, #New Param
useGeneBoundaries = TRUE,
useTSS = TRUE, #New Param
extendTSS = FALSE,
tileSize = 500,
ceiling = 4,
geneScaleFactor = 5, #New Param
scaleTo = 10000,
excludeChr = c("chrY", "chrM"),
blacklist = getBlacklist(proj),
threads = 1,
parallelParam = NULL,
subThreading = TRUE,
force = TRUE,
logFile = createLogFile(".addGeneScoreMatrix"))
scores <- getMatrixFromProject(proj, useMatrix = "GeneScoreMatrix")
scores_mat <- assays(scores)[[1]]
rownames(scores_mat) <- rowData(scores)$name
# sce <- SingleCellExperiment(list(scores=scores_mat),
# rowData = as.data.frame(rowData(scores)),
# colData = as.data.frame(colnames(scores_mat)))
#
# writeH5AD(sce, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/jupyter_notebooks/p2g_gene_activity_scores/archr_scores_tss", X_name = "scores")
ArchR gene activity scores computed using TSS, no gene body and PeakMatrix instead of TileMatrix
ArchR gene activity scores computed using TSS, no gene body and PeakMatrix instead of TileMatrix
proj <- loadArchRProject("12_Copy/")
proj <- addKathiGeneScoreMatrix(
proj,
genes = getGenes(proj),
peaks = getPeakSet(proj),
geneModel = "exp(-abs(x)/5000)",
matrixName = "GeneScoreMatrix",
extendUpstream = c(1000, 100000),
extendDownstream = c(1000, 100000),
#geneUpstream = 5000, #New Param
#geneDownstream = 0, #New Param
useGeneBoundaries = TRUE,
useTSS = TRUE, #New Param
extendTSS = FALSE,
tileSize = 500,
ceiling = 4,
geneScaleFactor = 5, #New Param
scaleTo = 10000,
excludeChr = c("chrY", "chrM"),
blacklist = getBlacklist(proj),
threads = 1,
parallelParam = NULL,
subThreading = TRUE,
force = TRUE,
logFile = createLogFile(".addKathiGeneScoreMat"))
scores <- getMatrixFromProject(proj, useMatrix = "GeneScoreMatrix")
scores_mat <- assays(scores)[[1]]
rownames(scores_mat) <- rowData(scores)$name
#
# sce <- SingleCellExperiment(list(scores=scores_mat),
# rowData = as.data.frame(rownames(scores_mat)),
# colData = as.data.frame(colnames(scores_mat)))
#
# writeH5AD(sce, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/jupyter_notebooks/p2g_gene_activity_scores/archr_scores_peak_based", X_name = "scores")
# sce <- SingleCellExperiment(list(p2g_mat = p2g_mat))
#
# writeH5AD(sce, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/jupyter_notebooks/p2g_gene_activity_scores/p2g_mat_250kb",
# X_name = "p2g_mat")
#
#
# sce <- SingleCellExperiment(list(peak_mat = peak_mat))
#
# writeH5AD(sce, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/jupyter_notebooks/p2g_gene_activity_scores/peak_mat",
# X_name = "peak_mat")
# cp_names <- colnames(colData(gene_expr))
# cp_names[20] <- "celltypes"
# colnames(colData(gene_expr)) <- cp_names
sce <- SingleCellExperiment(list(genes = expr_mat),
#rowData = as.data.frame(rownames(gene_expr)),
colData = as.data.frame(colData(gene_expr)))
# writeH5AD(sce, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/jupyter_notebooks/p2g_gene_activity_scores/gene_expr_mat",
# X_name = "genes")
#
#
# #p2g_mat_norm <- p2g_mat / rowSums(p2g_mat)
# scores <- p2g_mat %*% peak_mat
# scores <- t(t(scores) / colSums(scores))
# stopifnot(any(is.na(scores)) == FALSE)
# scores@x <- pmin(1e9, exp(scores@x) - 1)
#
#
#
# sce <- SingleCellExperiment(list(investigation = investigation))
#
# writeH5AD(sce, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/jupyter_notebooks/p2g_gene_activity_scores/investigation_scores",
# X_name = "investigation")
# latent embedding
emb <- getReducedDims(
ArchRProj = proj,
reducedDims = "atac_LSI_100000",
returnMatrix = TRUE,
dimsToUse = 1:30,
scaleDims = NULL,
corCutOff = 0.75
)
dim(emb)
sce <- SingleCellExperiment(list(embedding = emb))
writeH5AD(sce, "/omics/groups/OE0533/internal/katharina/scDoRI/gastrulation_data/jupyter_notebooks/p2g_gene_activity_scores/archr_lsi_embedding",
X_name = "embedding")
LS0tCnRpdGxlOiAiSW52ZXN0aWdhdGluZyBwMmdfbWF0IgpvdXRwdXQ6IAogIGh0bWxfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIHRvY19kZXB0aDogMgogICAgY29kZV9mb2xkaW5nOiBoaWRlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKICAgIHRoZW1lOiBjb3NtbwogICAgaGlnaGxpZ2h0OiB0ZXh0bWF0ZQotLS0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChjYWNoZSA9IEZBTFNFKQprbml0cjo6b3B0c19rbml0JHNldChyb290LmRpciA9ICIvb21pY3MvZ3JvdXBzL09FMDUzMy9pbnRlcm5hbC9rYXRoYXJpbmEvc2NEb1JJL2dhc3RydWxhdGlvbl9kYXRhIikKc2V0d2QoIi9vbWljcy9ncm91cHMvT0UwNTMzL2ludGVybmFsL2thdGhhcmluYS9zY0RvUkkvZ2FzdHJ1bGF0aW9uX2RhdGEiKQpzZXQuc2VlZCgxKQpgYGAKCmBgYHtyfQpzdXBwcmVzc1BhY2thZ2VTdGFydHVwTWVzc2FnZXMoewoKbGlicmFyeShBcmNoUikKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoU2luZ2xlQ2VsbEV4cGVyaW1lbnQpCmxpYnJhcnkoemVsbGtvbnZlcnRlcikKbGlicmFyeShkdHdjbHVzdCkKfSkKYGBgCgpgYGB7cn0KcHJvaiA8LSBsb2FkQXJjaFJQcm9qZWN0KCIxMV9hZGRlZF9SaWNhcmRzX3BlYWtzIiwgc2hvd0xvZ28gPSBGQUxTRSkKYGBgCgpgYGAje3J9CnByb2ogPC0gYWRkUGVhazJHZW5lTGlua3MoQXJjaFJQcm9qID0gcHJvaiwKICByZWR1Y2VkRGltcyAgPSAiYXRhY19MU0lfMTAwMDAwIiwKICB1c2VNYXRyaXggPSAiR2VuZUV4cHJlc3Npb25NYXRyaXgiLAogIG1heERpc3QgPSAyNTAwMDAsCiAgdmVyYm9zZSA9IFRSVUUKICApCgpwMmcgPC0gZ2V0UGVhazJHZW5lTGlua3MoCiAgQXJjaFJQcm9qID0gcHJvaiwKICBjb3JDdXRPZmYgPSAtMSwKICByZXNvbHV0aW9uID0gMSwKICBGRFJDdXRPZmYgPSAxZS0wNCwKICB2YXJDdXRPZmZBVEFDID0gLjI1LAogIHZhckN1dE9mZlJOQSA9IC4yNSwgCiAgcmV0dXJuTG9vcHMgPSBGQUxTRQopCmBgYAoKIyBQMkctbGluayBtYXRyaXggCgpgYGB7cn0KIyBzYXZlUkRTKHAyZywgIi9vbWljcy9ncm91cHMvT0UwNTMzL2ludGVybmFsL2thdGhhcmluYS9zY0RvUkkvZ2FzdHJ1bGF0aW9uX2RhdGEvUm1kcy9wZWFrMmdlbmVfbGlua3NfZW50aXJlX2Nocm9tb3NvbWVfMjVfMDRfMjAyMiIpCiNzYXZlUkRTKHAyZywgIi9vbWljcy9ncm91cHMvT0UwNTMzL2ludGVybmFsL2thdGhhcmluYS9zY0RvUkkvZ2FzdHJ1bGF0aW9uX2RhdGEvUm1kcy9uZXdfcGVhazJnZW5lX2xpbmtzXzIyXzA0XzIwMjIiKQpwMmcgPC0gcmVhZFJEUygiL29taWNzL2dyb3Vwcy9PRTA1MzMvaW50ZXJuYWwva2F0aGFyaW5hL3NjRG9SSS9nYXN0cnVsYXRpb25fZGF0YS9SbWRzL25ld19wZWFrMmdlbmVfbGlua3NfMjJfMDRfMjAyMiIpCmBgYAoKUmVhZCBpbiB0aGUgcGVhayBhY2Nlc3NpYmlsaXR5IG1hdHJpeCBhbmQgdGhlIGdlbmUgZXhwcmVzc2lvbiBtYXRyaXg6CgpgYGB7cn0KIyBnZXQgcGVhayBtYXRyaXgKcGVha3MgPC0gZ2V0TWF0cml4RnJvbVByb2plY3QocHJvaiwgdXNlTWF0cml4ID0gIlBlYWtNYXRyaXgiLCBiaW5hcml6ZSA9IEZBTFNFKQpwZWFrX21hdCA8LSBhc3NheXMocGVha3MpW1sxXV0KCiMgcmVhZCBpbiBnbmUgZXhwcmVzc3Npb24gbWF0cml4CmdlbmVfZXhwciA8LSBnZXRNYXRyaXhGcm9tUHJvamVjdChwcm9qLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHVzZU1hdHJpeCA9ICJHZW5lRXhwcmVzc2lvbk1hdHJpeCIpCmV4cHJfbWF0IDwtIGFzc2F5cyhnZW5lX2V4cHIpW1sxXV0Kcm93bmFtZXMoZXhwcl9tYXQpIDwtIHJvd0RhdGEoZ2VuZV9leHByKSRuYW1lCgojIHJlYWQgaW4gYXJjaHIgZ2VuZSBhY3Rpdml0eSBzY29yZXMKYXJjaHJfc2NvcmVzIDwtIGdldE1hdHJpeEZyb21Qcm9qZWN0KHByb2osIHVzZU1hdHJpeCA9ICJHZW5lU2NvcmVNYXRyaXgiKQoKY3BfbmFtZXMgPC0gY29sbmFtZXMoY29sRGF0YShhcmNocl9zY29yZXMpKQpjcF9uYW1lc1syMF0gPC0gImNlbGx0eXBlcyIKY29sbmFtZXMoY29sRGF0YShhcmNocl9zY29yZXMpKSA8LSBjcF9uYW1lcwoKYXJjaHJfc2NvcmVzX21hdCA8LSBhc3NheXMoYXJjaHJfc2NvcmVzKVtbMV1dCnJvd25hbWVzKGFyY2hyX3Njb3Jlc19tYXQpIDwtIHJvd0RhdGEoYXJjaHJfc2NvcmVzKSRuYW1lCmBgYAoKV2Ugd2lsbCBvbmx5IHVzZSBwZWFrcyBsaW5rZWQgdG8gaGlnaGx5IHZhcmlhYmxlIGdlbmVzIHRvIGNvbXB1dGUgZ2VuZQphY3Rpdml0eSBzY29yZXMuCgpgYGB7cn0KaHZnX2xpc3QgPC0gcmVhZC50YWJsZSgianVweXRlcl9ub3RlYm9va3MvaHZnX2xpc3QiLCBzZXAgPSAiLCIpJHgKCgojIGdldCBSTkEgaW5kZXggb2YgaHZnCm1ldGFfcm5hIDwtIHJvd0RhdGEoZ2VuZV9leHByKSAlPiUgYXMuZGF0YS5mcmFtZSgpICU+JSBtdXRhdGUocm93X2luZGV4ID0gc2VxKG5yb3coLikpKQppZHggPC0gKG1ldGFfcm5hICU+JSBmaWx0ZXIobmFtZSAlaW4lIGh2Z19saXN0KSkkcm93X2luZGV4CgpleHByX3N1YiA8LSBleHByX21hdFtpZHgsIF0KYGBgCgoKCmBgYHtyfQpsaW5rcyA8LSBwMmcgJT4lIGFzLmRhdGEuZnJhbWUoKSAlPiUgCiAgZmlsdGVyKENvcnJlbGF0aW9uID4gMC4yKSAlPiUgCiAgZmlsdGVyKGlkeFJOQSAlaW4lIGlkeCkgCgpzdG9waWZub3QoYWxsKGxpbmtzJENvcnJlbGF0aW9uID4gMCkpCmBgYAoKCgpDcmVhdGUgYSBwMmcgbGluayBtYXRyaXgKCmBgYHtyfQpwMmdfbWF0IDwtIHNwYXJzZU1hdHJpeChpID0gbGlua3MkaWR4Uk5BLAogICAgICAgICAgICAgaiA9IGxpbmtzJGlkeEFUQUMsCiAgICAgICAgICAgICB4PSBsaW5rcyRDb3JyZWxhdGlvbiwgCiAgICAgICAgICAgICBkaW1zID0gYyhkaW0oZXhwcl9tYXQpWzFdLAogICAgICAgICAgICAgZGltKHBlYWtfbWF0KVsxXSkpCgpyb3duYW1lcyhwMmdfbWF0KSA8LSByb3dEYXRhKGdlbmVfZXhwcikkbmFtZQoKCnJvd25hbWVzKHBlYWtfbWF0KSA8LSBzZXEuaW50KGRpbShwZWFrX21hdClbMV0pCmNvbG5hbWVzKHAyZ19tYXQpIDwtIHNlcS5pbnQoZGltKHBlYWtfbWF0KVsxXSkKYGBgCgoKCkZpbHRlciBhbmQgcHJlcGFyZSBwZWFrIG1hdHJpeCBhbmQgcDJnIGxpbmtzIG1hdHJpeDoKCmBgYHtyfQojIHJlbW92ZSBjb2x1bW5zIG9mIHBlYWtzIHdoaWNoIGFyZSBub3QgbGlua2VkIHRvIGFueSBwZWFrCnAyZ19tYXRfc3ViIDwtIHAyZ19tYXRbLCBjb2xTdW1zKHAyZ19tYXQpICE9IDBdCiMgdXNlIG9ubHkgaGlnaGx5IHZhcmlhYmxlIGdlbmVzCnAyZ19tYXRfc3ViIDwtIHAyZ19tYXRfc3ViW2h2Z19saXN0LCBdCiMgcmVtb3ZlIGFueSBnZW5lcyB3aGljaCBhcmUgbm90IGxpbmtlZCB0byBhbnkgcGVhawpwMmdfbWF0X3N1YiA8LSBwMmdfbWF0X3N1Yltyb3dTdW1zKHAyZ19tYXRfc3ViKSAhPSAwLCBdCnN0b3BpZm5vdChhbGwocm93bmFtZXMocDJnX21hdF9zdWIpICVpbiUgaHZnX2xpc3QpKQpzdG9waWZub3QoYW55KGlzLm5hKHAyZ19tYXRfc3ViKSA9PSBGQUxTRSkpCgojIGtlZXAgb25seSBwZWFrcyB3aGljaCBhcmUgbGlua2VkIHRvIGdlbmVzIGluIHRoZSBhY2Nlc3NpYmlsaXR5IG1hdHJpeApwZWFrX21hdF9zdWIgPC0gcGVha19tYXRbY29sbmFtZXMocDJnX21hdF9zdWIpLCBdCnN0b3BpZm5vdChyb3duYW1lcyhwZWFrX21hdF9zdWIpID09IGNvbG5hbWVzKHAyZ19tYXRfc3ViKSkKc3RvcGlmbm90KGFueShpcy5uYShwZWFrX21hdF9zdWIpID09IEZBTFNFKSkKc3RvcGlmbm90KGRpbShwZWFrX21hdF9zdWIpWzFdID09IGRpbShwMmdfbWF0X3N1YilbMl0pCgpleHByX21hdF9zdWIgPC0gZXhwcl9tYXRbYXMudmVjdG9yKHJvd25hbWVzKHAyZ19tYXRfc3ViKSksIF0KYGBgCgoKCgoKCiMjIyBGdW5jdGlvbiB0byBjb21wdXRlIGdlbmUgYWN0aXZpdHkgc2NvcmVzCgpgYGB7cn0KZ2VuZV9hY3Rpdml0eV9zY29yZXMgPC0gZnVuY3Rpb24ocGVha19tYXQsIHAyZ19tYXQpIHsKICAjcGVha19tYXRfc3Vic2V0IDwtIHBlYWtfbWF0W2NvbG5hbWVzKHAyZ19tYXQpLCBdCiAgIyBub3JtYWxpemUgdGhlIHAyZyBtYXRyaXggYnkgdGhlIHRvdGFsIG51bWJlciBvZiBwZWFrcyBsaW5rZWQgdG8gZWFjaCBnZW5lCiAgcDJnX21hdCA8LSBwMmdfbWF0IC8gcm93U3VtcyhwMmdfbWF0KQogIHByaW50KHBhc3RlMCgibm9ybWFsaXplZCB0aGUgcDJnIG1hdHJpeCIpKQogIHN0b3BpZm5vdChhbnkoaXMubmEocDJnX21hdCkpID09IEZBTFNFKQogICMgTm93IHdlIGNhbiBjb21wdXRlIGEgd2VpZ2h0ZWQgc3VtIG9mIHBlYWsyZ2VuZSBjb3JyZWxhdGlvbnMgZm9yIGVhY2gKICAjIHBlYWsgYW5kIGdlbmUKICBzY29yZXMgPC0gcDJnX21hdCAlKiUgcGVha19tYXQKICBwcmludChwYXN0ZTAoIkNvbXB1dGVkIHdlaWdodGVzIHN1bSBvZiBwZWFrcyBmb3IgZWFjaCBnZW5lIGFuZCBjZWxsIikpCiAgIyBjcmVhdGUgYSBkYXRhZnJhbWUgZm9yIGNvbXB1dGluZyB0aGUgbGluZWFyIG1vZGVsCiAgbGluZWFyX21vZGVsX2RmIDwtIGRhdGEuZnJhbWUoY2VsbCA9IGNvbG5hbWVzKHNjb3JlcyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0b3RhbF9hY3Rpdml0eSA9IGNvbFN1bXMoc2NvcmVzKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRvdGFsX3NpdGVzID0gY29sU3VtcyhwZWFrX21hdCkpCiAgIyBjb21wdXRlIGEgbGluZWFyIG1vZGVsCiAgYWN0aXZpdHlfbW9kZWwgPC0gc3RhdHM6OmxtKGxvZyh0b3RhbF9hY3Rpdml0eSkgfiBsb2codG90YWxfc2l0ZXMpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IGxpbmVhcl9tb2RlbF9kZikKICAjIGV4dHJhY3QgdGhlIGZpdHRlZCBtb2RlbAogIGxpbmVhcl9tb2RlbF9kZiRmaXR0ZWRfY3VydmUgPC0gZXhwKGFzLnZlY3RvcihwcmVkaWN0KGFjdGl2aXR5X21vZGVsLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0eXBlID0gInJlc3BvbnNlIikpKQogICMgY29tcHV0ZSBzaXplIGZhY3RvcnMgZnJvbSBmaXR0ZWQgbW9kZWwKICBzaXplX2ZhY3RvcnMgPC0gbWVhbihsaW5lYXJfbW9kZWxfZGYkZml0dGVkX2N1cnZlKSAvIGxpbmVhcl9tb2RlbF9kZiRmaXR0ZWRfY3VydmUKICAjIGNyZWF0ZSBkaWFnb25hbCBtYXRyaXggY29udGFpbmluZyB0aGUgc2l6ZSBmYWN0b3JzCiAgc2l6ZV9mYWN0b3JzX21hdCA8LSBNYXRyaXg6OkRpYWdvbmFsKHggPSBzaXplX2ZhY3RvcnMpCiAgI3Jvdy5uYW1lcyhzaXplX2ZhY3RvcnNfbWF0KSA8LSBsaW5lYXJfbW9kZWxfZGYkY2VsbAogICMgbm9ybWFsaXplIGJ5IGxpYnJhcnkgZGVwdGggc2l6ZSBmYWN0b3JzCiAgbm9ybV9zY29yZXMgPC0gTWF0cml4Ojp0KHNpemVfZmFjdG9yc19tYXQgJSolIE1hdHJpeDo6dChzY29yZXMpKQogIHByaW50KHBhc3RlMCgiTm9ybWFsaXplZCBmb3IgbGlicmFyeSBzaXplIikpCiAgIyBleHBvbmVudGlhdGUsIGJlY2F1c2UgUk5BIGNvdW50cyBhcmUgbG9nLW5vcm1hbGx5IGRpc3RyaWJ1dGVkCiAgbm9ybV9zY29yZXNAeCA8LSBwbWluKDFlOSwgZXhwKG5vcm1fc2NvcmVzQHgpIC0gMSkKICBwcmludChwYXN0ZTAoIkV4cG9uZW50aWF0ZWQgbWF0cml4IikpCiAgCiAgIyBmcmVlIHNvbWUgbWVtb3J5CiAgI3JtKHBlYWtfbWF0X3N1YnNldCkKICBybShhY3Rpdml0eV9tb2RlbCkKICBybShzY29yZXMpCiAgZ2MocmVzZXQgPSBUUlVFKQoKICAjIHNjYWxlIHdpdGggdG90YWwgYWN0aXZpdHkgc2NvcmVzIGFnYWluCiAgc2NhbGVfZmFjdG9ycyA8LSBNYXRyaXg6OkRpYWdvbmFsKHggPSAxL01hdHJpeDo6Y29sU3Vtcyhub3JtX3Njb3JlcykpCiAgcHJpbnQocGFzdGUwKCJEaXZpZGVkIGJ5IHRvdGFsIGFjdGl2aXR5IHRvIGdldCB2YWx1ZSBiZXR3ZWVuIHplcm8gYW5kIG9uZSIpKQogIAogIGZpbmFsX3Njb3JlcyA8LSBNYXRyaXg6OnQoc2NhbGVfZmFjdG9ycyAlKiUgTWF0cml4Ojp0KG5vcm1fc2NvcmVzKSkKCiAgcmV0dXJuKGZpbmFsX3Njb3JlcykKCn0KCmBgYAoKYGBge3J9CnAyZ19zY29yZXMgPC0gZ2VuZV9hY3Rpdml0eV9zY29yZXMocGVha19tYXRfc3ViLCBwMmdfbWF0X3N1YikKYGBgCgoKCgoKIyBFeGFtcGxlIG9mIHAyZyBsaW5rcyB3aXRoaW4gMjUwa2IKCgpgYGB7cn0KY3BfbmFtZXMgPC0gY29sbmFtZXMoY29sRGF0YShnZW5lX2V4cHIpKQpjcF9uYW1lc1syMF0gPC0gImNlbGx0eXBlcyIKY29sbmFtZXMoY29sRGF0YShnZW5lX2V4cHIpKSA8LSBjcF9uYW1lcwoKI3Jvd25hbWVzKGV4cHJfbWF0KSA8LSByb3dEYXRhKGdlbmVfZXhwcikkbmFtZQpnZW5lcyA8LSBleHByX21hdFthcy52ZWN0b3Iocm93bmFtZXMocDJnX3Njb3JlcykpLCBdCgpzdG9waWZub3QoYW55KHJvd25hbWVzKGdlbmVzKSA9PSByb3duYW1lcyhwMmdfc2NvcmVzKSkpCgoKCiMgY3JlYXRlIG1hdHJpeCB0byBzdG9yZSBhZ2dyZWdhdGVzCmV4cHJfYWdnIDwtIG1hdHJpeChkYXRhID0gMCwgCiAgICAgICAgICAgICAgICAgICBucm93ID0gZGltKGdlbmVzKVsxXSwKICAgICAgICAgICAgICAgICAgIG5jb2wgPSBsZW5ndGgodW5pcXVlKGNvbERhdGEoZ2VuZV9leHByKSRjZWxsdHlwZXMpKSwKICAgICAgICAgICAgICAgICAgIGRpbW5hbWVzICA9IGxpc3Qocm93bmFtZXMocDJnX3Njb3JlcyksCiAgICAgICAgICAgICAgICAgICB1bmlxdWUoY29sRGF0YShnZW5lX2V4cHIpJGNlbGx0eXBlcykpKQoKCiMgZmlsbCBtYXRyaXgKZm9yIChjZWxsdHlwZSBpbiB1bmlxdWUoY29sRGF0YShnZW5lX2V4cHIpJGNlbGx0eXBlcykpewogIGJhcmNvZGVzIDwtIHJvd25hbWVzKGNvbERhdGEoZ2VuZV9leHByKSAlPiUgCiAgICAgICAgICAgICAgICAgICAgICAgICBhcy5kYXRhLmZyYW1lKCkgJT4lIAogICAgICAgICAgICAgICAgICAgICAgICAgZmlsdGVyKGNlbGx0eXBlcyA9PSBjZWxsdHlwZSkpCiAgZXhwcl9hZ2dbLCBjZWxsdHlwZV0gPC0gcm93U3VtcyhnZW5lc1ssIGJhcmNvZGVzXSkKfQoKCgpwMmdfc2NvcmVfYWdnIDwtIG1hdHJpeChkYXRhID0gMCwgCiAgICAgICAgICAgICAgICAgICAgICAgIG5yb3cgPSBkaW0ocDJnX3Njb3JlcylbMV0sCiAgICAgICAgICAgICAgICAgICAgICAgIG5jb2wgPSBsZW5ndGgodW5pcXVlKGNvbERhdGEoZ2VuZV9leHByKSRjZWxsdHlwZXMpKSwKICAgICAgICAgICAgICAgICAgICAgICAgZGltbmFtZXMgPSBsaXN0KHJvd25hbWVzKHAyZ19zY29yZXMpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdW5pcXVlKGNvbERhdGEoZ2VuZV9leHByKSRjZWxsdHlwZXMpKSkKCmZvciAoY2VsbHR5cGUgaW4gdW5pcXVlKGNvbERhdGEoZ2VuZV9leHByKSRjZWxsdHlwZXMpKXsKICBiYXJjb2RlcyA8LSByb3duYW1lcyhjb2xEYXRhKGdlbmVfZXhwcikgJT4lIAogICAgICAgICAgICAgICAgICAgICAgICAgYXMuZGF0YS5mcmFtZSgpICU+JSAKICAgICAgICAgICAgICAgICAgICAgICAgIGZpbHRlcihjZWxsdHlwZXMgPT0gY2VsbHR5cGUpKQogIHAyZ19zY29yZV9hZ2dbLCBjZWxsdHlwZV0gPC0gcm93U3VtcyhwMmdfc2NvcmVzWywgYmFyY29kZXNdKQp9CmBgYAoKCgoKQ29ycmVsYXRpb25zIGJldHdlZW4gYWdncmVnYXRlZCBnZW5lIGV4cHJlc3Npb24gYW5kIGFnZ3JlZ2F0ZWQgcDJnIHNjb3JlcyBmb3IgCmNlbGx0eXBlcy4KCgoKYGBge3J9CmNvcnJlbGF0aW9uc18yNTBrYiA9IGMoKQpmb3IgKGkgaW4gc2VxLmludChkaW0ocDJnX3Njb3JlX2FnZylbMV0pKXsKICByb3dhIDwtIGV4cHJfYWdnW2ksIF0KICByb3dhIDwtIHJvd2EgLSBtZWFuKHJvd2EpCiAgcm93YSA8LSByb3dhIC8gc2Qocm93YSkKICAKICByb3diIDwtIHAyZ19zY29yZV9hZ2dbaSwgXQogIHJvd2IgPC0gcm93YiAtIG1lYW4ocm93YikKICByb3diIDwtIHJvd2IgLyBzZChyb3diKQogIAogIGNvcnJfdmFsdWUgPSBtZWFuKHJvd2EgKiByb3diKQogIGNvcnJlbGF0aW9uc18yNTBrYiA8LSBjKGNvcnJlbGF0aW9uc18yNTBrYiwgY29ycl92YWx1ZSkKICAKfSAKbmFtZXMoY29ycmVsYXRpb25zXzI1MGtiKSA8LSByb3duYW1lcyhwMmdfc2NvcmVfYWdnKQoKcGxvdF8yNTBrYiA8LSBnZ3Bsb3QoKSArIGdlb21faGlzdG9ncmFtKGFlcyh4ID0gY29ycmVsYXRpb25zXzI1MGtiKSwgYmlucyA9IDIwMCwgZmlsbD0iIzY5YjNhMiIpICsKICBsYWJzKCJnZW5lIGFjdGl2aXR5IHNjb3JlcyBjb21wdXRlZCBiYXNlZCBvbiBwMmcgbGlua3Mgd2l0aGluIDI1MGtiIG9mIGdlbmUiKQpwbG90XzI1MGtiCmBgYAoKCgojIGtubiBjZWxsIGFnZ3JlZ2F0ZXMgZnJvbSBBcmNoUgoKYGBgI3tyfQpybmFfa25uIDwtIHJlYWRSRFMoIjExX2FkZGVkX1JpY2FyZHNfcGVha3MvUGVhazJHZW5lTGlua3Mvc2VSTkEtR3JvdXAtS05OLnJkcyIpCnJuYV9hZ2dfbWF0IDwtIGFzc2F5cyhybmFfa25uKVtbMV1dCnJvd25hbWVzKHJuYV9hZ2dfbWF0KSA8LSByb3dEYXRhKHJuYV9rbm4pJG5hbWUKCmNlbGxfYWdnX2xpc3QgPC0gbWV0YWRhdGEocm5hX2tubilbWzFdXQoKCmtubl9hZ2dyZWdhdGVzIDwtIGZ1bmN0aW9uKG1hdHJpeCwgY2VsbF9hZ2dfbGlzdCl7CiAgIyBlbXB0eSBtYXRyaXggdG8gc3RvcmUgYWdncmVnYXRlcwogIGFnZyA8LSBtYXRyaXgoZGF0YSA9IDAsCiAgICAgICAgICAgICAgICBucm93ID0gZGltKG1hdHJpeClbMV0sCiAgICAgICAgICAgICAgICBuY29sID0gbGVuZ3RoKGNlbGxfYWdnX2xpc3QpLAogICAgICAgICAgICAgICAgZGltbmFtZXMgPSBsaXN0KHJvd25hbWVzKG1hdHJpeCksIE5VTEwpKQogIAogIGZvciAoaSBpbiBzZXEuaW50KGxlbmd0aChjZWxsX2FnZ19saXN0KSkpIHsKICAgIGFnZ1ssIGldIDwtIHJvd1N1bXMobWF0cml4WywgY2VsbF9hZ2dfbGlzdFtbaV1dXSkKICB9CiAgcmV0dXJuKGFnZykKfQoKCnJuYV9hZ2cgPC0ga25uX2FnZ3JlZ2F0ZXMoZXhwcl9tYXRfc3ViLCBjZWxsX2FnZ19saXN0KQphZ2dfcDJnX2tubiA8LSBrbm5fYWdncmVnYXRlcyhwMmdfc2NvcmVzLCBjZWxsX2FnZ19saXN0KQoKYXJjaHJfa25uIDwtIGFyY2hyX3Njb3Jlc19tYXRbYXMudmVjdG9yKHJvd25hbWVzKGFnZ19wMmdfa25uKSksXQphZ2dfYXJjaHJfa25uIDwtIGtubl9hZ2dyZWdhdGVzKGFyY2hyX2tubiwgY2VsbF9hZ2dfbGlzdCkKYGBgCgoKYGBgI3tyfQphcmNocl9rbm4gPC0gcm93d2lzZV9jb3JyZWxhdGlvbnMocm5hX2FnZywgYWdnX2FyY2hyX2tubiwgIkFyY2hyIGdlbmUgYWN0aXZpdHkgc2NvcmVzIikKcDJnX2tubiA8LSByb3d3aXNlX2NvcnJlbGF0aW9ucyhybmFfYWdnLCBhZ2dfcDJnX2tubiwgIlBlYWstdG8tZ2VuZSBsaW5rcyBhY3Rpdml0eSBzY29yZXMiKQoKY293cGxvdDo6cGxvdF9ncmlkKGFyY2hyX2tubltbMl1dLCBwMmdfa25uW1syXV0sIG5jb2wgPSAyKQoKZ2dwbG90KCkgKyBnZW9tX2RlbnNpdHlfMmRfZmlsbGVkKGFlcyh4ID0gcDJnX2tubltbMV1dLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5ID0gYXJjaHJfa25uW1sxXV0pLCBhbHBoYSA9IC41KSArCiAgZ2VvbV9wb2ludChhZXMoeCA9IHAyZ19rbm5bWzFdXSwgeSA9IGFyY2hyX2tubltbMV1dKSkgKwogIGdlb21fbGluZShhZXMoeCA9IHAyZ19rbm5bWzFdXSwgeSA9IHAyZ19rbm5bWzFdXSksIGNvbCA9ICJyZWQiKQogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJOb25lIikgCgpgYGAKCiMgRnVuY3Rpb25zCgojIyMgRnVuY3Rpb24gdG8gcHJlcCBwZWFrIGFjY2Vzc2liaWxpdHkgbWF0cml4LCBnZW5lIGV4cHJlc3Npb24gbWF0cml4IGFuZCBwMmctbGluayBtYXRyaXgKCmBgYCN7cn0KcHJlcF9wZWFrX3AyZyA8LSBmdW5jdGlvbihwZWFrX21hdCwgcDJnX21hdCwgaHZnX2xpc3QsIGV4cHJfbWF0KXsKICAjcm93bmFtZXMocGVha19tYXQpIDwtIHNlcS5pbnQoZGltKHBlYWtfbWF0KVsxXSkKICAjY29sbmFtZXMocDJnX21hdCkgPC0gc2VxLmludChkaW0ocDJnX21hdClbMl0pCiAgCiAgIyByZW1vdmUgY29sdW1ucyBvZiBwZWFrcyB3aGljaCBhcmUgbm90IGxpbmtlZCB0byBhbnkgcGVhawogIHAyZ19tYXRfc3ViIDwtIHAyZ19tYXRbLCBjb2xTdW1zKHAyZ19tYXQpICE9IDBdCiAgIyB1c2Ugb25seSBoaWdobHkgdmFyaWFibGUgZ2VuZXMKICBwMmdfbWF0X3N1YiA8LSBwMmdfbWF0X3N1YltodmdfbGlzdCwgXQogICMgcmVtb3ZlIGFueSBnZW5lcyB3aGljaCBhcmUgbm90IGxpbmtlZCB0byBhbnkgcGVhawogIHAyZ19tYXRfc3ViIDwtIHAyZ19tYXRfc3ViW3Jvd1N1bXMocDJnX21hdF9zdWIpICE9IDAsIF0KICBzdG9waWZub3QoYWxsKHJvd25hbWVzKHAyZ19tYXRfc3ViKSAlaW4lIGh2Z19saXN0KSkKICBzdG9waWZub3QoYW55KGlzLm5hKHAyZ19tYXRfc3ViKSA9PSBGQUxTRSkpCiAgCiAgIyBrZWVwIG9ubHkgcGVha3Mgd2hpY2ggYXJlIGxpbmtlZCB0byBnZW5lcyBpbiB0aGUgYWNjZXNzaWJpbGl0eSBtYXRyaXgKICBwZWFrX21hdF9zdWIgPC0gcGVha19tYXRbY29sbmFtZXMocDJnX21hdF9zdWIpLCBdCiAgc3RvcGlmbm90KHJvd25hbWVzKHBlYWtfbWF0X3N1YikgPT0gY29sbmFtZXMocDJnX21hdF9zdWIpKQogIHN0b3BpZm5vdChhbnkoaXMubmEocGVha19tYXRfc3ViKSA9PSBGQUxTRSkpCiAgc3RvcGlmbm90KGRpbShwZWFrX21hdF9zdWIpWzFdID09IGRpbShwMmdfbWF0X3N1YilbMl0pCiAgCiAgZXhwcl9tYXRfc3ViIDwtIGV4cHJfbWF0W2FzLnZlY3Rvcihyb3duYW1lcyhwMmdfbWF0X3N1YikpLCBdCiAgc3RvcGlmbm90KHJvd25hbWVzKGV4cHJfbWF0X3N1YikgPT0gcm93bmFtZXMocDJnX21hdF9zdWIpKQogIHJldHVybihsaXN0KHBlYWtfbWF0X3N1YiwgcDJnX21hdF9zdWIsIGV4cHJfbWF0X3N1YikpCn0KYGBgCgoKCgojIyMgRnVuY3Rpb24gdG8gY3JlYXRlIGNlbGx0eXBlIGFnZ3JlZ2F0ZXM6CgpgYGB7cn0KIyB0aGUgZGF0YSBtYXRyaXggbmVlZHMgdG8gYmUgb2YgZGltZW5zaW9uIGZlYXR1cmVzIHggY2VsbHMKIyB0aGUgY29sdW1uIG9mIHRoZSBjb2xEYXRhIG9mIHRoZSBzY2Ugb2JqZWN0IHdoZXJlIGNlbGx0eXBlcyBhcmUgc3RvcmVkCiMgbmVlZHMgdG8gYmUgY2FsbGVkICJjZWxsdHlwZXMiCmNyZWF0ZV9jZWxsdHlwZV9hZ2dyZWdhdGVzIDwtIGZ1bmN0aW9uKHNjZSwgZGF0YV9tYXRyaXgsIGNlbGx0eXBlcykgewogICNjcmVhdGUgZW1wdHkgbWF0cml4IHRvIHN0b3JlIGFnZ3JlZ2F0ZXMKICBhZ2cgPC0gbWF0cml4KGRhdGEgPSAwLAogICAgICAgICAgICAgICAgbnJvdyA9IGRpbShkYXRhX21hdHJpeClbMV0sCiAgICAgICAgICAgICAgICBuY29sID0gbGVuZ3RoKGNlbGx0eXBlcyksCiAgICAgICAgICAgICAgICBkaW1uYW1lcyA9IGxpc3Qocm93bmFtZXMoZGF0YV9tYXRyaXgpLCBjZWxsdHlwZXMpKQogIAoKICBmb3IgKGNlbGx0eXBlIGluIGNlbGx0eXBlcykgewogICAgYmFyY29kZXMgPC0gcm93bmFtZXMoY29sRGF0YShzY2UpICU+JQogICAgICAgICAgICAgICAgICAgICAgICAgICBhcy5kYXRhLmZyYW1lKCkgJT4lCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGZpbHRlcihjZWxsdHlwZXMgPT0gY2VsbHR5cGUpKQogICAgYWdnWywgY2VsbHR5cGVdIDwtIHJvd1N1bXMoZGF0YV9tYXRyaXhbLCBiYXJjb2Rlc10pCiAgfQogIHJldHVybihhZ2cpCn0KCgpjcmVhdGVfY2VsbHR5cGVfYWdncmVnYXRlc19wMmdfc2NvcmVzIDwtIGZ1bmN0aW9uKGdlbmVfZXhwcl9zY2UsIHAyZ19zY29yZV9tYXRyaXgsIGNlbGx0eXBlcykgewogICAgI2NyZWF0ZSBlbXB0eSBtYXRyaXggdG8gc3RvcmUgYWdncmVnYXRlcwogIGFnZyA8LSBtYXRyaXgoZGF0YSA9IDAsCiAgICAgICAgICAgICAgICBucm93ID0gZGltKHAyZ19zY29yZV9tYXRyaXgpWzFdLAogICAgICAgICAgICAgICAgbmNvbCA9IGxlbmd0aChjZWxsdHlwZXMpLAogICAgICAgICAgICAgICAgZGltbmFtZXMgPSBsaXN0KHJvd25hbWVzKHAyZ19zY29yZV9tYXRyaXgpLCBjZWxsdHlwZXMpKQogIAoKICBmb3IgKGNlbGx0eXBlIGluIGNlbGx0eXBlcykgewogICAgYmFyY29kZXMgPC0gcm93bmFtZXMoY29sRGF0YShnZW5lX2V4cHJfc2NlKSAlPiUKICAgICAgICAgICAgICAgICAgICAgICAgICAgYXMuZGF0YS5mcmFtZSgpICU+JQogICAgICAgICAgICAgICAgICAgICAgICAgICBmaWx0ZXIoY2VsbHR5cGVzID09IGNlbGx0eXBlKSkKICAgIGFnZ1ssIGNlbGx0eXBlXSA8LSByb3dTdW1zKHAyZ19zY29yZV9tYXRyaXhbLCBiYXJjb2Rlc10pCiAgfQogIHJldHVybihhZ2cpCn0KCmBgYAoKCgojIyMgRnVuY3Rpb24gdG8gY29tcHV0ZSByb3ctd2lzZSBjb3JyZWxhdGlvbnMgYmV0d2VlbiB0d28gbWF0cmljZXM6CgpgYGB7cn0Kcm93d2lzZV9jb3JyZWxhdGlvbnMgPC0gZnVuY3Rpb24oTWF0cml4QSwgTWF0cml4QiwgbmFtZSkgewogIGludGVyc2VjdF9nZW5lcyA8LSBpbnRlcnNlY3Qocm93bmFtZXMoTWF0cml4QSksIHJvd25hbWVzKE1hdHJpeEIpKQogIE1hdHJpeEEgPC0gTWF0cml4QVtpbnRlcnNlY3RfZ2VuZXMsIF0KICBNYXRyaXhCIDwtIE1hdHJpeEJbaW50ZXJzZWN0X2dlbmVzLCBdCiAgY29ycmVsYXRpb25zIDwtIGMoKQogIGZvciAoaSBpbiBzZXEuaW50KGRpbShNYXRyaXhBKVsxXSkpIHsKICAgIHJvd0EgPC0gTWF0cml4QVtpLCBdCiAgICByb3dBIDwtIHJvd0EgLSBtZWFuKHJvd0EpCiAgICBpZiAoc2Qocm93QSkgIT0gMCkgewogICAgICByb3dBIDwtIHJvd0EgLyBzZChyb3dBKQogICAgfQogIAogICAgcm93QiA8LSBNYXRyaXhCW2ksIF0KICAgIHJvd0IgPC0gcm93QiAtIG1lYW4ocm93QikKICAgIGlmIChzZChyb3dCKSAhPSAwKXsKICAgICAgcm93QiA8LSByb3dCIC8gc2Qocm93QikKICAgIH0KICAgIAogICAgY29ycl92YWx1ZSA8LSBtZWFuKHJvd0EgKiByb3dCKQogICAgY29ycmVsYXRpb25zIDwtIGMoY29ycmVsYXRpb25zLCBjb3JyX3ZhbHVlKQogIH0KICBuYW1lcyhjb3JyZWxhdGlvbnMpIDwtIHJvd25hbWVzKE1hdHJpeEEpCiAgcGxvdCA8LSBnZ3Bsb3QoKSArIGdlb21faGlzdG9ncmFtKGFlcyh4ID0gY29ycmVsYXRpb25zKSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJpbnMgPSAyMDAsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmaWxsPSIjNjliM2EyIikgKyBsYWJzKHRpdGxlID0gcGFzdGUwKG5hbWUpKQogIHJldHVybihsaXN0KGNvcnJlbGF0aW9ucywgcGxvdCkpCn0KYGBgCgoKCiMgQ29ycmVsYXRpb25zIHdpdGggQXJjaFIgZ2VuZSBhY3Rpdml0eSBzY29yZXMKCmBgYHtyfQphcmNocl9zY29yZXNfc3ViIDwtIGFyY2hyX3Njb3Jlc19tYXRbYXMudmVjdG9yKHJvd25hbWVzKGV4cHJfYWdnKSksIF0KCm5hbWUgPC0gIkFyY2hSX3Njb3JlcyIKCmFyY2hyX3Njb3Jlc19hZ2cgPC0gY3JlYXRlX2NlbGx0eXBlX2FnZ3JlZ2F0ZXMoYXJjaHJfc2NvcmVzLCBhcmNocl9zY29yZXNfc3ViLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB1bmlxdWUoY29sRGF0YShhcmNocl9zY29yZXMpJGNlbGx0eXBlcykpCnN0b3BpZm5vdChhbnkoaXMubmEoYXJjaHJfc2NvcmVzX2FnZykpID09IEZBTFNFKQoKY29ycnMgPC0gcm93d2lzZV9jb3JyZWxhdGlvbnMoZXhwcl9hZ2csIGFyY2hyX3Njb3Jlc19hZ2csIG5hbWUpCmFyY2hyX2NvcnIgPC0gY29ycnNbMV0KY293cGxvdDo6cGxvdF9ncmlkKHBsb3RfMjUwa2IgKyBsYWJzKHRpdGxlID0gIlAyZy1saW5rcyBhY3Rpdml0eSBzY29yZXMiKSwgY29ycnNbWzJdXSwgbmNvbCA9IDIpCmBgYAoKCgpgYGB7ciwgZmlnLndpZHRoID0gNSwgZmlnLmhlaWdodD01fQpnZ3Bsb3QoKSArICNnZW9tX2RlbnNpdHkyZF9maWxsZWQoYWVzKHggPSBjb3JyZWxhdGlvbnNfMjUwa2IsIHkgPSBjb3Jyc1sxXSkpICMrCiAgZ2VvbV9wb2ludChhZXMoeCA9IGNvcnJlbGF0aW9uc18yNTBrYiwgeSA9IGNvcnJzW1sxXV0pKSArCiAgbGFicyh4ID0gIkNvcnJlbGF0aW9uIGdlbmUgZXhwcmVzc2lvbiBhbmQgcDJnIGFjdGl2aXR5IHNjb3JlcyIsCiAgICAgICB5ID0gIkNvcnJlbGF0aW9uIGdlbmUgZXhwcmVzc2lvbiBhbmQgQXJjaFIgZ2VuZSBhY3Rpdml0eSBzY29yZXMiKQoKCiMgZ2dwbG90KCkgKyBnZW9tX3BvaW50KGFlcyh4ID0gYXJjaHJfc2NvcmVzX3N1YlsiSGJhLWExIixdLCB5ID0gcDJnX3Njb3Jlc1siSGJhLWExIixdKSkKIyBnZ3Bsb3QoKSArIGdlb21fcG9pbnQoYWVzKHggPSBhcmNocl9zY29yZXNfc3ViWyJHYXRhNiIsXSwgeSA9IHAyZ19zY29yZXNbIkhiYS1hMSIsXSkpCgpgYGAKCgoKCgoKCiMgRGlzdGFuY2Ugd2VpZ2h0cwoKCiMjIyBGdW5jdGlvbiB0byBjb21wdXRlIGRpc3RhbmNlLXdlaWdodGVkIGdlbmUgYWN0aXZpdHkgc2NvcmVzIGZyb20gcDJnIGxpbmtzCgohISEhISEgQ2hlY2sgYWdhaW4hIEJlY2F1c2UgaGVyZSBzb21ldGhpbmcgaXMgd3Jvbmcgd2l0aCB0aGUgd2F5IEkgY29tcHV0ZSB0aGUgZGlzdGFuY2Ugd2VpZ2h0cyEgU29tZXRpbWVzIEkgbmVlZCB0byB1c2UgdGhlIHN0YXJ0IGNvb3JkaW5hdGUgaW5zdGVhZCBvZiB0aGUgZW5kIGNvb3JkaW5hdGUuIFRyeSBhbHdheXMgdXNpbmcgdGhlIGdlbmUgc3RhcnQgY29vcmRpbmF0ZSBpbnN0ZWFkIG9mIHN3YXBwaW5nIHN0YXJ0CmFuZCBlbmQgY29vcmRpbmF0ZXMgaW4gdGhlIGRhdGFmcmFtZS4gTWF5YmUgdGhpcyBpcyBkb25lIGF1dG9tYXRpY2FsbCB3aGVuIGNvbnZlcnRlZCAKdG8gZGF0YWZyYW1lPwoKYGBge3J9CiMgQXMgaW5wdXQgZm9yIHRoaXMgZnVuY3Rpb24gaXQgaXMgYmVzdCB0byB1c2Ugb25seSB0aGUgbW9zdCBoaWdobHkgdmFyaWFibGUgZ2VuZXMKZGlzdGFuY193ZWlnaHRlZF9nZW5lX2FjdGl2aXR5X3Njb3JlcyA8LSBmdW5jdGlvbihwMmdfbWF0X3N1YiwgZ2VuZU1vZGVsID0gImV4cCgtZGlzdGFuY2UvNTAwMCkiLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB3ZWlnaHQgPSA1MDAwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBwZWFrX21hdCwgbGlua3MsIHAyZ19vcmlnaW5hbCwgZ2VuZV9leHByKXsKICBhdGFjX2dyYW5nZXMgPC0gbWV0YWRhdGEocDJnX29yaWdpbmFsKVtbMV1dCiAgI3JuYV9ncmFuZ2VzIDwtIG1ldGFkYXRhKHAyZ19vcmlnaW5hbClbWzJdXQogIGdlbmVfYW5ubyA8LSByb3dEYXRhKGdlbmVfZXhwcikKICAKICAjIGNyZWF0ZSBnZW5lIGFubm90YXRpb25zIHdpdGggc3RhcnQgY29vcmRpbmF0ZSBvZiBlYWNoIGdlbmUKICAjIHN1YnNldCB0byBjb250YWluIG9ubHkgZ2VuZXMgd2hpY2ggYXJlIGluY2x1ZGVkIGluIG91ciBwZWFrMmdlbmUgbWF0cml4CiAgZ2VuZV9hbm5vIDwtIGdlbmVfYW5ubyAlPiUgYXMuZGF0YS5mcmFtZSgpICU+JQogICAgbXV0YXRlKGlkeFJOQSA9IHNlcShucm93KC4pKSkgJT4lIAogICAgZmlsdGVyKG5hbWUgJWluJSByb3duYW1lcyhwMmdfbWF0X3N1YikpICU+JQogICAgbXV0YXRlKHN0cmFuZCA9IGlmZWxzZShzdHJhbmQgPT0gMSwgIisiLCAiLSIpKSAlPiUgCiAgICBtdXRhdGUoc3RhcnRfY29vcmQgPSBpZmVsc2Uoc3RyYW5kID09ICIrIiwgc3RhcnQsIGVuZCkpICU+JSAKICAgIHJlbmFtZShnZW5lID0gbmFtZSkgIyU+JSBHUmFuZ2VzKCkKCiAgIyBzdWJzZXQgYXRhYyBncmFuZ2VzICYgZ2V0IG1pZGRsZSBvZiBlYWNoIHBlYWsKICBwb3NfYXRhY19ncmFuZ2VzIDwtIGF0YWNfZ3JhbmdlcyAgJT4lIAogICAgYXMuZGF0YS5mcmFtZSgpICU+JQogICAgbXV0YXRlKGlkeEFUQUMgPSBzZXEobnJvdyguKSkpICU+JSAKICAgICMgZ3JvdXBfYnkoc2VxbmFtZXMpICU+JQogICAgIyBtdXRhdGUoaWR4ID0gc2VxX2Fsb25nKHNlcW5hbWVzKSkgJT4lIAogICAgIyB1bmdyb3VwICU+JQogICAgI3RpZHlyOjp1bml0ZShjaHJfaWR4LCBzZXFuYW1lcywgaWR4LCByZW1vdmUgPSBGQUxTRSwgc2VwID0gIl8iKSAlPiUgCiAgICBmaWx0ZXIoaWR4QVRBQyAlaW4lIGNvbG5hbWVzKHAyZ19tYXRfc3ViKSkgJT4lIAogICAgbXV0YXRlKG1pZGRsZSA9IHN0YXJ0ICsgMzAwKSAjJT4lIEdSYW5nZXMoKSAKICAKICAjVE9ETzogRmlsdGVyIGZvciBnZW5lcyEKICBzdG9waWZub3QobGVuZ3RoKHVuaXF1ZShsaW5rcyRpZHhBVEFDKSkgPT0gZGltKHBvc19hdGFjX2dyYW5nZXMpW1sxXV0pCiAgc3RvcGlmbm90KGxlbmd0aCh1bmlxdWUobGlua3MkaWR4Uk5BKSkgPT0gZGltKGdlbmVfYW5ubylbWzFdXSkKICAjcDJnX2ZpbHQgPC0gcDJnX29yaWdpbmFsICU+JSBhcy5kYXRhLmZyYW1lKCkgJT4lIGZpbHRlcihnZW5lICVpbiUgcm93bmFtZXMocDJnX21hdCkpCiAgCiAgCiAgIyBjb21iaW5lIHRoZSB0aHJlZSBkYXRhZnJhbWVzCiAgcDJnX2pvaW4gPC0gbGVmdF9qb2luKGxpbmtzLCBhcy5kYXRhLmZyYW1lKHBvc19hdGFjX2dyYW5nZXMpLAogICAgICAgICAgICAgICAgICAgICAgICBieSA9ICJpZHhBVEFDIikKICBwMmdfam9pbiA8LSBsZWZ0X2pvaW4ocDJnX2pvaW4sIGFzLmRhdGEuZnJhbWUoZ2VuZV9hbm5vKSwKICAgICAgICAgICAgICAgICAgICAgICAgYnkgPSAiaWR4Uk5BIiwgc3VmZml4ID0gYygiLmF0YWMiLCAiLnJuYSIpKQoKICAjIGNvbXB1dGUgZGlzdGFuY2UgYW5kIGRpc3RhbmNlIHdlaWdodHMgCiAgcDJnX2pvaW4gPC0gcDJnX2pvaW4gJT4lIAogICAgbXV0YXRlKGRpc3RhbmNlID0gYWJzKHN0YXJ0X2Nvb3JkIC0gbWlkZGxlKSkgJT4lCiAgICBtdXRhdGUoZGlzdGFuY2Vfd2VpZ2h0ID0gZXZhbChwYXJzZSh0ZXh0PWdlbmVNb2RlbCkpKQogIAogIAogIHAxIDwtIHAyZ19qb2luICU+JSBnZ3Bsb3QoKSArCiAgICBnZW9tX2hpc3RvZ3JhbShhZXMoeCA9IGRpc3RhbmNlKSwgYmlucyA9IDEwMCkgKwogICAgbGFicyh0aXRsZSA9ICJEaXN0YW5jZSIsIHggPSAiZGlzdGFuY2UiKSArCiAgICBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQgID0gNTAwMCwgY29sb3IgPSAicmVkIikKICAKICBwMiA8LSBwMmdfam9pbiAlPiUgZ2dwbG90KCkgKwogICAgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSAoZGlzdGFuY2Vfd2VpZ2h0KSksIGJpbnMgPSAxMDApICsKICAgIHNjYWxlX3lfbG9nMTAoKSArCiAgICBsYWJzKHRpdGxlID0gIkRpc3RhbmNlIFdlaWdodHMiLCB4ID0gImRpc3RhbmNlIHdlaWdodHMiKQoKICBjb3dwbG90OjpwbG90X2dyaWQocDEsIHAyLCBuY29sID0gMikKICAKICAKICAjIGNyZWF0ZSBkaXN0YW5jZSB3ZWlnaHQgbWF0cml4CiAgcDJnX2R3IDwtIHNwYXJzZU1hdHJpeChpID0gcDJnX2pvaW4kaWR4Uk5BLAogICAgICAgICAgICAgICAgICAgICAgICAgaiA9IHAyZ19qb2luJGlkeEFUQUMsCiAgICAgICAgICAgICAgICAgICAgICAgICB4ID0gcDJnX2pvaW4kZGlzdGFuY2Vfd2VpZ2h0LAogICAgICAgICAgICAgICAgICAgICAgICAgZGltcyA9IGMoZGltKGFzc2F5cyhnZW5lX2V4cHIpW1sxXV0pWzFdLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGltKHBlYWtfbWF0KVsxXSksCiAgICAgICAgICAgICAgICAgICAgICAgICBkaW1uYW1lcyA9IGxpc3Qocm93RGF0YShnZW5lX2V4cHIpJG5hbWUgLCAKICAgICAgICAgICAgICAgICAgICAgICAgIHNlcS5pbnQoZGltKHBlYWtfbWF0KVsxXSkpKQoKCiAgcDJnX2R3IDwtIHAyZ19kd1thcy52ZWN0b3Iocm93bmFtZXMocDJnX21hdF9zdWIpKSwgY29sbmFtZXMocDJnX21hdF9zdWIpXQogIAogICMgZWxlbWVudHdpc2UgbWF0cml4IG11bHRpcGxpY2F0aW9uCiAgd2VpZ2h0ZWRfcDJnX21hdCA8LSBwMmdfbWF0X3N1YiAqIHAyZ19kdwogIAogIHByaW50KHBhc3RlKGxlbmd0aCh3aGljaChyb3dTdW1zKHdlaWdodGVkX3AyZ19tYXQpID09IDApKSwgImdlbmVzIGhhdmUgb25seSB6ZXJvIGNvcnJlbGF0aW9uIHZhbHVlcywgc28gd2Ugd2lsbCByZW1vdmUgdGhlbS4iKSkKICB3ZWlnaHRlZF9wMmdfbWF0IDwtIHdlaWdodGVkX3AyZ19tYXRbcm93U3Vtcyh3ZWlnaHRlZF9wMmdfbWF0KSAhPSAwLCBdCiAgcHJpbnQocGFzdGUwKCJXZSBhcmUgbGVmdCB3aXRoICIsIGRpbSh3ZWlnaHRlZF9wMmdfbWF0KVsxXSwgIiBnZW5lcyIpKQogIAogICMgY29tcHV0ZSBnZW5lIGFjdGl2aXR5IHNjb3JlcyBiYXNlZCBvbiBkaXN0YW5jZS13ZWlnaHRlZCBwZWFrMmdlbmUgbWF0cml4CiAgd2VpZ2h0ZWRfc2NvcmVzIDwtIGdlbmVfYWN0aXZpdHlfc2NvcmVzKHBlYWtfbWF0X3N1Yiwgd2VpZ2h0ZWRfcDJnX21hdCkKICAKICByZXR1cm4od2VpZ2h0ZWRfc2NvcmVzKSAKfQpgYGAKCmBgYHtyfQp3ZWlnaHRlZF9zY29yZXMgPC0gZGlzdGFuY193ZWlnaHRlZF9nZW5lX2FjdGl2aXR5X3Njb3JlcyhwMmdfbWF0X3N1YiwgZ2VuZU1vZGVsID0gImV4cCgtZGlzdGFuY2UvNTAwMCkiLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB3ZWlnaHQgPSA1MDAwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBwZWFrX21hdCwgbGlua3MsIHAyZywgZ2VuZV9leHByKQpgYGAKCgpgYGB7cn0KbW9kZWxfbGlzdCA8LSBjKCJleHAoLWFicyhkaXN0YW5jZSkvNTAwMCkiLCAiZXhwKC1hYnMoZGlzdGFuY2UpLzUwMDAwKSIsCiAgICAgICAgICAgICAgICAiZXhwKC1hYnMoZGlzdGFuY2UpLzUwMDAwMCkiLCAiZXhwKC1hYnMoZGlzdGFuY2UpLzUwMDAwMDApIikKCiMgcmVhZCBpbiBrbm4Kcm5hX2tubiA8LSByZWFkUkRTKCIxMV9hZGRlZF9SaWNhcmRzX3BlYWtzL1BlYWsyR2VuZUxpbmtzL3NlUk5BLUdyb3VwLUtOTi5yZHMiKQpjZWxsX2FnZ19saXN0IDwtIG1ldGFkYXRhKHJuYV9rbm4pW1sxXV0KCgojIEZ1bmN0aW9uIHRvIGNvbXB1dGUgYWdncmVnYXRlcyB3aXRoIGtubiBmcm9tIEFyY2hSCmtubl9hZ2dyZWdhdGVzIDwtIGZ1bmN0aW9uKG1hdHJpeCwgY2VsbF9hZ2dfbGlzdCl7CiAgIyBlbXB0eSBtYXRyaXggdG8gc3RvcmUgYWdncmVnYXRlcwogIGFnZyA8LSBtYXRyaXgoZGF0YSA9IDAsCiAgICAgICAgICAgICAgICBucm93ID0gZGltKG1hdHJpeClbMV0sCiAgICAgICAgICAgICAgICBuY29sID0gbGVuZ3RoKGNlbGxfYWdnX2xpc3QpLAogICAgICAgICAgICAgICAgZGltbmFtZXMgPSBsaXN0KHJvd25hbWVzKG1hdHJpeCksIE5VTEwpKQogIAogIGZvciAoaSBpbiBzZXEuaW50KGxlbmd0aChjZWxsX2FnZ19saXN0KSkpIHsKICAgIGFnZ1ssIGldIDwtIHJvd1N1bXMobWF0cml4WywgY2VsbF9hZ2dfbGlzdFtbaV1dXSkKICB9CiAgcmV0dXJuKGFnZykKfQoKCiMgYWdncmVnYXRlIGZvciBnZW5lIGV4cHJlc3Npb24sIEFyY2hSIGdlbmUgYWN0aXZpdHkgc2NvcmVzIGFuZCBzaW1wbGUgcDJnIGxpbmtzCnJuYV9hZ2cgPC0ga25uX2FnZ3JlZ2F0ZXMoZXhwcl9tYXRfc3ViLCBjZWxsX2FnZ19saXN0KQphcmNocl9rbm4gPC0gYXJjaHJfc2NvcmVzX21hdFthcy52ZWN0b3Iocm93bmFtZXMocm5hX2FnZykpLF0KYWdnX2FyY2hyX2tubiA8LSBrbm5fYWdncmVnYXRlcyhhcmNocl9rbm4sIGNlbGxfYWdnX2xpc3QpCmFnZ19wMmdfa25uIDwtIGtubl9hZ2dyZWdhdGVzKHAyZ19zY29yZXMsIGNlbGxfYWdnX2xpc3QpCgojIGNvbXB1dGUgcm93d2lzZSBjb3JyZWxhdGlvbnMKYXJjaHJfa25uIDwtIHJvd3dpc2VfY29ycmVsYXRpb25zKHJuYV9hZ2csIGFnZ19hcmNocl9rbm4sICJBcmNociBnZW5lIGFjdGl2aXR5IHNjb3JlcyIpCnAyZ19rbm4gPC0gcm93d2lzZV9jb3JyZWxhdGlvbnMocm5hX2FnZywgYWdnX3AyZ19rbm4sICJQZWFrLXRvLWdlbmUgbGlua3MgYWN0aXZpdHkgc2NvcmVzIikKY293cGxvdDo6cGxvdF9ncmlkKGFyY2hyX2tubltbMl1dLCBwMmdfa25uW1syXV0sIG5jb2wgPSAyKQoKCiMgcHJlcGFyZSBsaXN0cyB0byBzdG9yZSBjb3JyZWxhdGlvbiB2ZWN0b3JzIGFuZCBjb3JyZWxhdGlvbiBoaXN0b2dyYW1zCmNvcnJfbGlzdCA8LSBsaXN0KGFyY2hyX2tubltbMV1dLCBwMmdfa25uW1sxXV0pCgojIGNvbXB1dGUgdGhlIGRpc3RhbmNlLXdlaWdodGVkIGdlbmUgYWN0aXZpdHkgc2NvcmVzIGZyb20gcDJnIGxpbmtzIHVzaW5nIGRpZmZlcmVudCAKIyBkaXN0YW5jZSB3ZWlnaHQgbW9kZWxzCmZvciAobW9kZWwgaW4gbW9kZWxfbGlzdCl7CiAgd2VpZ2h0ZWRfc2NvcmVzIDwtIGRpc3RhbmNfd2VpZ2h0ZWRfZ2VuZV9hY3Rpdml0eV9zY29yZXMocDJnX21hdF9zdWIsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGdlbmVNb2RlbCA9IG1vZGVsLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB3ZWlnaHQgPSA1MDAwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBwZWFrX21hdCA9IHBlYWtfbWF0LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxpbmtzID0gbGlua3MsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHAyZ19vcmlnaW5hbCA9IHAyZywgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZ2VuZV9leHByID0gZ2VuZV9leHByKQogIGFnZ19kaXN0IDwtIGtubl9hZ2dyZWdhdGVzKHdlaWdodGVkX3Njb3JlcywgY2VsbF9hZ2dfbGlzdCkKICBkaXN0X2tubiA8LSByb3d3aXNlX2NvcnJlbGF0aW9ucyhybmFfYWdnLCBhZ2dfZGlzdCwgbmFtZSA9IHBhc3RlMCgiUDJnIGFjdGl2aXR5IHNjb3JlcywgZGlzdGFuY2Ugd2VpaHRlZCwgbW9kZWwgPSAiLCBtb2RlbCkpCiAgc3RvcGlmbm90KGFueShpcy5uYShkaXN0X2tubikpID09IEZBTFNFKQogIAogIGNvcnJfbGlzdCA8LSBhcHBlbmQoY29ycl9saXN0LCBkaXN0X2tubltbMV1dKQogIHByaW50KGRpc3Rfa25uW1syXV0pCiAgI2NvcnJfcGxvdHNfbGlzdCA8LSBhcHBlbmQoY29ycl9wbG90c19saXN0LCBkaXN0X2tubltbMl1dKQogIAogIHBsb3QgPC0gZ2dwbG90KCkgKyAjZ2VvbV9kZW5zaXR5XzJkX2ZpbGxlZChhZXMoeCA9IGNvcnJfbGlzdFtbaV1dLCAKICAgICAgICAgICAgICAgICAgICAgICMgICAgICAgICAgICAgICAgeSA9IGNvcnJfbGlzdFtbMV1dKSwgYWxwaGEgPSAuNSkgKwogIGdlb21fcG9pbnQoYWVzKHggPSBkaXN0X2tubltbMV1dLCB5ID0gY29ycl9saXN0W1sxXV0pKSArCiAgZ2VvbV9saW5lKGFlcyh4ID0gZGlzdF9rbm5bWzFdXSwgeSA9IGRpc3Rfa25uW1sxXV0pLCBjb2wgPSAicmVkIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJOb25lIikgICsKICBsYWJzKHggPSAiQ29ycmVsYXRpb24gYmV0d2VlbiBnZW5lIGV4cHJlc3Npb24gYW5kIHAyZyBhY3Rpdml0eSBzY29yZXMiLAogICAgICAgIHRpdGxlID0gcGFzdGUwKG1vZGVsKSwKICAgICAgICB5ID0gIkNvcnJlbGF0aW9uIGJldHdlZW4gZ2VuZSBleHByZXNzaW9uIGFuZCBBcmNoUiBnZW5lIGFjdGl2aXR5IHNjb3JlcyIpCiAgcHJpbnQocGxvdCkKfQoKCiMgY293cGxvdDo6cGxvdF9ncmlkKGNvcnJfcGxvdHNfbGlzdCwgbmNvbCA9IDIpCiMgZG8uY2FsbCh3aGF0ID0gY293cGxvdDo6cGxvdF9ncmlkLCBhcmdzID0gYXBwZW5kKGNvcnJfcGxvdHNfbGlzdCksIAojICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxpc3QobmNvbCA9IDIpKSMsIG5yb3cgPSBsZW5ndGgoY29ycl9wbG90c19saXN0KS8yKSkpCiMgCiMgcGxvdF9saXN0IDwtIGxpc3QoKQojIGZvciAoaSBpbiBsZW5ndGgoY29ycl9saXN0KSl7CiMgICBybmFfYXJjaHJfY29yciA8LSBjb3JyX2xpc3RbWzFdXQojICAgaWYgKGkgIT0gMSl7CiMgICAgICNjb3JyX3ZlY3RvciA8LSBjb3JyX2xpc3RbWzFdXQojICAgcGxvdCA8LSBnZ3Bsb3QoKSArIGdlb21fZGVuc2l0eV8yZF9maWxsZWQoYWVzKHggPSBjb3JyX2xpc3RbW2ldXSwgCiMgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5ID0gY29ycl9saXN0W1sxXV0pLCBhbHBoYSA9IC41KSArCiMgICBnZW9tX3BvaW50KGFlcyh4ID0gY29ycl9saXN0W1tpXV0sIHkgPSBjb3JyX2xpc3RbWzFdXSkpICsKIyAgIGdlb21fbGluZShhZXMoeCA9IGNvcnJfbGlzdFtbaV1dLCB5ID0gY29ycl9saXN0W1tpXV0pLCBjb2wgPSAicmVkIikgKwojICAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIk5vbmUiKSAKIyAgICNwbG90X2xpc3QgPC0gYXBwZW5kKHBsb3RfbGlzdCwgcGxvdCkKIyAgIAojICAgfQojIH0KIyAKIyBkby5jYWxsKHdoYXQgPSBjb3dwbG90OjpwbG90X2dyaWQsIGFyZ3MgPSBhcHBlbmQocGxvdF9saXN0KSkKYGBgCgoKCiMgR2VuZSB3aW5kb3csIG5vIGRpc3RhbmNlIHdlaWdodHMKCgpgYGB7ciwgZmlnLndpZHRoPTEwfQojIEFzIGlucHV0IGZvciB0aGlzIGZ1bmN0aW9uIGl0IGlzIGJlc3QgdG8gdXNlIG9ubHkgdGhlIG1vc3QgaGlnaGx5IHZhcmlhYmxlIGdlbmVzCmNvbXB1dGVfZ2VuZV93aW5kb3dfc2NvcmUgPC0gZnVuY3Rpb24ocDJnX21hdF9zdWIsIHdlaWdodCA9IDUwMDAwLCBwZWFrX21hdCwgbGlua3MsIHAyZ19vcmlnaW5hbCwgZ2VuZV9leHByKXsKICBhdGFjX2dyYW5nZXMgPC0gbWV0YWRhdGEocDJnX29yaWdpbmFsKVtbMV1dCiAgI3JuYV9ncmFuZ2VzIDwtIG1ldGFkYXRhKHAyZ19vcmlnaW5hbClbWzJdXQogIGdlbmVfYW5ubyA8LSByb3dEYXRhKGdlbmVfZXhwcikKICAKICAjIGNyZWF0ZSBnZW5lIGFubm90YXRpb25zIHdpdGggc3RhcnQgY29vcmRpbmF0ZSBvZiBlYWNoIGdlbmUKICAjIHN1YnNldCB0byBjb250YWluIG9ubHkgZ2VuZXMgd2hpY2ggYXJlIGluY2x1ZGVkIGluIG91ciBwZWFrMmdlbmUgbWF0cml4CiAgZ2VuZV9hbm5vIDwtIGdlbmVfYW5ubyAlPiUgYXMuZGF0YS5mcmFtZSgpICU+JQogICAgbXV0YXRlKGlkeFJOQSA9IHNlcShucm93KC4pKSkgJT4lIAogICAgZmlsdGVyKG5hbWUgJWluJSByb3duYW1lcyhwMmdfbWF0X3N1YikpICU+JQogICAgbXV0YXRlKHN0cmFuZCA9IGlmZWxzZShzdHJhbmQgPT0gMSwgIisiLCAiLSIpKSAlPiUKICAgIG11dGF0ZShzdGFydF9jb29yZCA9IGlmZWxzZShzdHJhbmQgPT0gIisiLCBzdGFydCwgZW5kKSkgJT4lIAogICAgcmVuYW1lKGdlbmUgPSBuYW1lKSAjJT4lIEdSYW5nZXMoKQoKICAjZ2VuZVJlZ2lvbnMgPC0gZ2VuZV9hbm5vICU+JSBHUmFuZ2VzKCkKICBnZW5lX3JlZ2lvbnMgIDwtIHJlc2l6ZShnZW5lX2Fubm8gJT4lIEdSYW5nZXMoKSwgd2lkdGggPSAxKQogIGV4dGVuZGVkR2VuZVJlZ2lvbiA8LSAoc3VwcHJlc3NXYXJuaW5ncyhleHRlbmRHUihnZW5lX3JlZ2lvbnMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHVwc3RyZWFtID0gMTAwMDAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkb3duc3RyZWFtID0gMTAwMDAwKSkpCiAgIyBzdWJzZXQgYXRhYyBncmFuZ2VzICYgZ2V0IG1pZGRsZSBvZiBlYWNoIHBlYWsKICBwb3NfYXRhY19ncmFuZ2VzIDwtIGF0YWNfZ3JhbmdlcyAgJT4lIAogICAgYXMuZGF0YS5mcmFtZSgpICU+JQogICAgbXV0YXRlKGlkeEFUQUMgPSBzZXEobnJvdyguKSkpICU+JSAKICAgICMgZ3JvdXBfYnkoc2VxbmFtZXMpICU+JQogICAgIyBtdXRhdGUoaWR4ID0gc2VxX2Fsb25nKHNlcW5hbWVzKSkgJT4lIAogICAgIyB1bmdyb3VwICU+JQogICAgI3RpZHlyOjp1bml0ZShjaHJfaWR4LCBzZXFuYW1lcywgaWR4LCByZW1vdmUgPSBGQUxTRSwgc2VwID0gIl8iKSAlPiUgCiAgICBmaWx0ZXIoaWR4QVRBQyAlaW4lIGNvbG5hbWVzKHAyZ19tYXRfc3ViKSkgJT4lIAogICAgbXV0YXRlKG1pZGRsZSA9IHN0YXJ0ICsgMzAwKSAjJT4lIEdSYW5nZXMoKSAKICAKICAjVE9ETzogRmlsdGVyIGZvciBnZW5lcyEKICBzdG9waWZub3QobGVuZ3RoKHVuaXF1ZShsaW5rcyRpZHhBVEFDKSkgPT0gZGltKHBvc19hdGFjX2dyYW5nZXMpW1sxXV0pCiAgc3RvcGlmbm90KGxlbmd0aCh1bmlxdWUobGlua3MkaWR4Uk5BKSkgPT0gZGltKGdlbmVfYW5ubylbWzFdXSkKICAjcDJnX2ZpbHQgPC0gcDJnX29yaWdpbmFsICU+JSBhcy5kYXRhLmZyYW1lKCkgJT4lIGZpbHRlcihnZW5lICVpbiUgcm93bmFtZXMocDJnX21hdCkpCiAgCiAgCiAgICAjIGZpbmQgb3ZlcmxhcHBpbmcgcGVha3MgYW5kIGdlbmUgd2luZG93IGluIGNocm9tb3NvbWUtYXdhcmUgZmFzaGlvbgogIHRtcCA8LSBzdXBwcmVzc1dhcm5pbmdzKGZpbmRPdmVybGFwcyhleHRlbmRlZEdlbmVSZWdpb24sIHBvc19hdGFjX2dyYW5nZXMgJT4lIEdSYW5nZXMoKSkpCiAgCiAgcHJpbnQocGFzdGUwKCJPdXQgb2YgIiwgc3ViamVjdExlbmd0aCh0bXApLCAiIHBlYWtzIG9ubHkgIiwKICAgICAgICAgICAgICAgbGVuZ3RoKHVuaXF1ZShzdWJqZWN0SGl0cyh0bXApKSksICIgcGVha3MgYXJlIGZvdW5kIHdpdGhpbiBnZW5lIHdpbmRvdyBvZiAyMDBrYi4iKSkKICAKICAKICAjIyMgc29tZSBwbG90cwogIHByaW50KHRtcCAlPiUgYXMuZGF0YS5mcmFtZSgpICU+JSAKICAgICAgICAgZ3JvdXBfYnkocXVlcnlIaXRzKSAlPiUgIyBnZW5lIHJlZ2lvbgogICAgICAgICBzdW1tYXJpemUobiA9IG4oKSkgJT4lICMgZ2V0IG51bWJlciBvZiBwZWFrcyBvdmVybGFwcGluZyB3aXRoIGEgZ2VuZSByZWdpb24KICAgICAgICAgZ2dwbG90KCkgKyBnZW9tX2hpc3RvZ3JhbShhZXMoeCA9IG4pLCBiaW5zID0gMTAwLCBmaWxsPSIjNjliM2EyIikgKwogICAgICAgICBsYWJzKHRpdGxlID0gIm51bWJlciBvZiBwZWFrcyBwZXIgZ2VuZSByZWdpb24gb2Ygc2l6ZSArLy0gMTAwa2IgZnJvbSBUU1MiLAogICAgICAgICAgICAgeCA9ICJudW1iZXIgb2YgcGVha3Mgd2l0aGluIHdpbmRvdyIsKSkKICAKICAKICAKICAjIGNvbWJpbmUgdGhlIHRocmVlIGRhdGFmcmFtZXMKICBwMmdfam9pbiA8LSBsZWZ0X2pvaW4obGlua3MsIGFzLmRhdGEuZnJhbWUocG9zX2F0YWNfZ3JhbmdlcyksCiAgICAgICAgICAgICAgICAgICAgICAgIGJ5ID0gImlkeEFUQUMiKQogIHAyZ19qb2luIDwtIGxlZnRfam9pbihwMmdfam9pbiwgYXMuZGF0YS5mcmFtZShnZW5lX2Fubm8pLAogICAgICAgICAgICAgICAgICAgICAgICBieSA9ICJpZHhSTkEiLCBzdWZmaXggPSBjKCIuYXRhYyIsICIucm5hIikpCgogICMgY29tcHV0ZSBkaXN0YW5jZSBhbmQgZGlzdGFuY2Ugd2VpZ2h0cyAKICBwMmdfam9pbiA8LSBwMmdfam9pbiAlPiUgCiAgICBtdXRhdGUoZGlzdGFuY2UgPSBhYnMoc3RhcnRfY29vcmQgLSBtaWRkbGUpKSMgJT4lCiAgICMgbXV0YXRlKGRpc3RhbmNlX3dlaWdodCA9IGV2YWwocGFyc2UodGV4dD1nZW5lTW9kZWwpKSkKICAKICAKICBwMSA8LSBwMmdfam9pbiAlPiUgZ2dwbG90KCkgKwogICAgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSBkaXN0YW5jZSksIGJpbnMgPSAxMDApICsKICAgIGxhYnModGl0bGUgPSAiRGlzdGFuY2UiLCB4ID0gImRpc3RhbmNlIikgKwogICAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ICA9IDEwMDAwMCwgY29sb3IgPSAicmVkIikgCgogIAogICMgcDIgPC0gcDJnX2pvaW4gJT4lIGdncGxvdCgpICsKICAjICAgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSAoZGlzdGFuY2Vfd2VpZ2h0KSksIGJpbnMgPSAxMDApICsKICAjICAgc2NhbGVfeV9sb2cxMCgpICsKICAjICAgbGFicyh0aXRsZSA9ICJEaXN0YW5jZSBXZWlnaHRzIiwgeCA9ICJkaXN0YW5jZSB3ZWlnaHRzIikgCgogIHByaW50KGNvd3Bsb3Q6OnBsb3RfZ3JpZChwMSkpIyksICBuY29sID0gMikpCiAgCiAgCiAgCiAgCiAgICAKICAjIGNyZWF0ZSBhIGRhdGFmcmFtZSBvZiBhbGwgcGVha3Mgd2hpY2ggb3ZlcmxhcCB0aGVpciBjb3JyZXNwb25kaW5nIGdlbmUgd2luZG93CiAgcGVha3NfaW5fZ2VuZV93aW5kb3cgPC0gZGF0YS5mcmFtZShnZW5lID0gZ2VuZV9yZWdpb25zW3F1ZXJ5SGl0cyh0bXApXSRnZW5lLCAKICAgICAgICAgICAgIHBlYWsgPSAocG9zX2F0YWNfZ3JhbmdlcyAlPiUgR1JhbmdlcygpKVtzdWJqZWN0SGl0cyh0bXApXSRpZHhBVEFDKSAlPiUgCiAgICB1bml0ZShwZWFrX2dlbmVfd2luZG93LCBnZW5lLCBwZWFrLCBzZXAgPSAiIyIsIHJlbW92ZSA9IEZBTFNFKQogIAogICMgZmlsdGVyIHRoZSBwMmcgbGluayBkYXRhZnJhbWUgZm9yIG9ubHkgcGVha3Mgd2hpY2ggYXJlIHdpdGhpbiBhIGdlbmUgd2luZG93CiAgY29ycl93aW5kb3cgPC0gcDJnX2pvaW4gJT4lCiAgICB1bml0ZShwZWFrX2dlbmVfd2luZG93LCBnZW5lLCBpZHhBVEFDLCBzZXAgPSAiIyIsIHJlbW92ZSA9IEZBTFNFKSAlPiUKICAgIGZpbHRlcihwZWFrX2dlbmVfd2luZG93ICVpbiUgcGVha3NfaW5fZ2VuZV93aW5kb3ckcGVha19nZW5lX3dpbmRvdykgCgoKICAjIyMgUExPVFMKICAKICBwMSA8LSBjb3JyX3dpbmRvdyAlPiUgCiAgICBnZ3Bsb3QoKSArCiAgICBnZW9tX2hpc3RvZ3JhbShhZXMoeCA9IENvcnJlbGF0aW9uKSwgYmlucyA9IDIwMCwgZmlsbCA9ICIjNjliM2EyIikgKwogICAgbGFicyh0aXRsZSA9ICJDb3JyZWxhdGlvbiB2YWx1ZXMgb2YgcGVha3MgZm91bmQgd2l0aGluIGdlbmUgd2luZG93cyIpCiAgCiAgcDIgPC0gY29ycl93aW5kb3cgJT4lIAogICAgZ2dwbG90KCkgKwogICAgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSBkaXN0YW5jZSksIGJpbnMgPSAyMDAsIGZpbGwgPSAiIzY5YjNhMiIpICsKICAgIGxhYnModGl0bGUgPSAiRGlzdGFuY2UgYmV0d2VlbiBwZWFrcyBhbmQgZ2VuZXMgZm91bmQgd2l0aGluIGdlbmUgd2luZG93cyBhbmQgVFNTIikKICAKICBwMyA8LSBjb3JyX3dpbmRvdyAlPiUgCiAgICBtdXRhdGUoYmluID0gY3V0X3dpZHRoKGRpc3RhbmNlLCB3aWR0aD0xMDAwMCwgYm91bmRhcnk9MCkpICU+JSAKICAgIGdncGxvdCgpICsKICAgIGdlb21fYm94cGxvdChhZXMoeCA9IGJpbiwgeSA9IENvcnJlbGF0aW9uKSwgZmlsbCA9ICIjNjliM2EyIikgKwogICAgbGFicyh0aXRsZSA9ICJEaXN0YW5jZSBhbmQgQ29ycmVsYXRpb24gd2l0aGluIGdlbmUgd2luZG93LCAxMDAwYnAgYmlucyIsCiAgICAgICAgIHggPSAiRGlzdGFuY2UgKDEwMDBicCBiaW5zKSIpCiAgcHJpbnQoY293cGxvdDo6cGxvdF9ncmlkKHAxLCBwMiwgcDMsIG5jb2wgPSAyKSkKICAKICAKICBwMSA8LSBnZ3Bsb3QoKSArIAogICAgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSByb3dTdW1zKHAyZ19tYXRfc3ViID4gMCkpLCBiaW5zID0gMjAwLCBmaWxsID0gIiM2OWIzYTIiKSArCiAgICBzY2FsZV95X2xvZzEwKCkgKwogICAgbGFicyh0aXRsZSA9ICJOdW1iZXIgb2YgcGVha3MgY29ycmVsYXRlZCB3aXRoIGVhY2ggZ2VuZSIsIAogICAgICAgICB4ID0gIm51bWJlciBvZiBwZWFrcyIsIHkgPSAibG9nMTAoY291bnQpIikgCiAgICAKICAKICBwMiA8LSBnZ3Bsb3QoKSArIAogICAgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSBjb2xTdW1zKHAyZ19tYXRfc3ViID4gMCkpLCBiaW5zID0gNzAsIGZpbGwgPSAiIzY5YjNhMiIpICsKICAgIHNjYWxlX3lfbG9nMTAoKSArCiAgICBsYWJzKHRpdGxlID0gIk51bWJlciBvZiBnZW5lcyBjb3JyZWxhdGVkIHdpdGggZWFjaCBwZWFrIiwKICAgICAgICAgeSA9ICJsb2cxMChjb3VudCkiLCB4ID0gIm51bWJlciBvZiBnZW5lcyIpCiAgCiAgcDMgPC0gZ2dwbG90KCkgKyAKICAgIGdlb21faGlzdG9ncmFtKGFlcyh4ID0gcm93U3VtcyhwMmdfbWF0X3N1YiA+IDApKSwgYmlucyA9IDIwMCwgZmlsbCA9ICIjNjliM2EyIikgKwogICAgbGFicyh0aXRsZSA9ICJOdW1iZXIgb2YgcGVha3MgY29ycmVsYXRlZCB3aXRoIGVhY2ggZ2VuZSIsIAogICAgICAgICB4ID0gIm51bWJlciBvZiBwZWFrcyIsIHkgPSAiY291bnQiKSAKICAgIAogIAogIHA0IDwtIGdncGxvdCgpICsgCiAgICBnZW9tX2hpc3RvZ3JhbShhZXMoeCA9IGNvbFN1bXMocDJnX21hdF9zdWIgPiAwKSksIGJpbnMgPSA3MCwgZmlsbCA9ICIjNjliM2EyIikgKwogICAgbGFicyh0aXRsZSA9ICJOdW1iZXIgb2YgZ2VuZXMgY29ycmVsYXRlZCB3aXRoIGVhY2ggcGVhayIsCiAgICAgICAgIHkgPSAiY291bnQiLCB4ID0gIm51bWJlciBvZiBnZW5lcyIpCiAgCiAgcHJpbnQoY293cGxvdDo6cGxvdF9ncmlkKHAxLCBwMiwgcDMsIHA0LCBuY29sID0gMikpCgogIAoKICAKICAKICAKICBwZWFrX21pZGRsZV9yZWdpb24gPC0gcG9zX2F0YWNfZ3JhbmdlcyAlPiUgR1JhbmdlcygpCiAgIyBhZGQgdGhlIGhhbGYgd2lkdGggdG8gdGhlIHN0YXJ0IG9mIGVhY2ggcGVhawogIHN0YXJ0KHBlYWtfbWlkZGxlX3JlZ2lvbikgPSBzdGFydChwZWFrX21pZGRsZV9yZWdpb24pICsgCiAgICBmbG9vcih3aWR0aChwZWFrX21pZGRsZV9yZWdpb24pIC8gMikKICAjIHJlc2l6ZSB0aGUgcmFuZ2VzIHNvIHdlIG9ubHkgaGF2ZSB0aGUgbWlkZGxlIG9mIGVhY2ggcGVhawogIHBlYWtfbWlkZGxlX3JlZ2lvbiA8LSByZXNpemUocGVha19taWRkbGVfcmVnaW9uLCAxLCAic3RhcnQiKQogIAogICMgY29tcHV0ZSB0aGUgZGlzdGFuY2VzIGJldHdlZW4gcGVhayBtaWRkbGUgYW5kIGdlbmUgVFNTIG9mIGFsbCBwZWFrcyB3aGljaCAKICAjIG92ZXJsYXAgd2l0aCBhIGdlbmUgd2luZG93CiAgZGlzdGFuY2UgPC0gZGlzdGFuY2UocmFuZ2VzKGdlbmVfcmVnaW9ucylbcXVlcnlIaXRzKHRtcCldLCAKICAgICAgICAgICAgICAgIHJhbmdlcyhyZXNpemUocGVha19taWRkbGVfcmVnaW9uLCB3aWR0aCA9IDEpKVtzdWJqZWN0SGl0cyh0bXApXSkKICAKICAKICAjIyMgUExPVAogICMgcDEgPC0gZ2dwbG90KCkgKyBnZW9tX2hpc3RvZ3JhbShhZXMoeCA9IGRpc3RhbmNlKSwgYmlucyA9IDIwMCkgKwogICMgICBzY2FsZV95X2xvZzEwKCkgKwogICMgICBsYWJzKHRpdGxlID0gIkRpc3RhbmNlIGJldHdlZW4gcGVhayBtaWRkbGUgYW5kIGdlbmUgVFNTIHdpdGhpbiBhIGdlbmUgd2luZG93IiwKICAjICAgICAgICB5ID0gImxvZzEwKGNvdW50KSIpICsKICAjICAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gMTAwMDAwLCBjb2xvciA9ICJyZWQiKQogIAogIAogIAogIGlzTWludXMgPC0gQmlvY0dlbmVyaWNzOjp3aGljaChzdHJhbmQoZ2VuZV9yZWdpb25zKSA9PSAiLSIpCiAgIyBzdWJ0cmFjdCB0aGUgZ2VuZSBzdGFydCBjb29yZGluYXRlIGZyb20gdGhlIHRpbGUgc3RhcnQgY29vcmRpbmF0ZSAtPiByZWxhdGl2ZSBkaXN0YW5jZXMKICBzaWduRGlzdCA8LSBzaWduKHN0YXJ0KHBlYWtfbWlkZGxlX3JlZ2lvbilbc3ViamVjdEhpdHModG1wKV0gLSAKICAgICAgICAgICAgICAgICAgICAgc3RhcnQocmVzaXplKGdlbmVfcmVnaW9ucywxLCJzdGFydCIpKVtxdWVyeUhpdHModG1wKV0pCiAgIyBjb252ZXJ0IHRoZSBkaXJlY3Rpb24gb2YgZGlzdGFuY2UgZm9yIGFsbCBkaXN0YW5jZXMgY29ycmVzcG9uZGluZyB0byB0aGUgbmVnYXRpdmUgc3RyYW5kCiAgc2lnbkRpc3RbaXNNaW51c10gPC0gc2lnbkRpc3RbaXNNaW51c10gKiAtMQogIAogIAogIGRpc3RhbmNlIDwtIGRpc3RhbmNlICogc2lnbkRpc3QKICAKICAKICAKICAjIyMjIFBMT1QKICBwMiA8LSBnZ3Bsb3QoKSArIGdlb21faGlzdG9ncmFtKGFlcyh4ID0gZGlzdGFuY2UpLCBiaW5zID0gNTAwKSArIAogICAgc2NhbGVfeV9sb2cxMCgpICsKICAgIGxhYnModGl0bGUgPSAiRGlzdHJpYnV0aW9uIG9mIHJlbGF0aXZlIGRpc3RhbmNlcyBiZXR3ZWVuIGdlbmVzIGFuZCBwZWFrcyB3aXRoaW4gYSBnZW5lIHJlZ2lvbiIsCiAgICAgICAgIHggPSAicmVsYXRpdmUgZGlzdGFuY2UgdG8gVFNTIiwgeSA9ICJsb2cxMChjb3VudCkiKSArIAogICAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gYygxMDAwMDAsIC0xMDAwMDApLCBjb2xvciA9ICJyZWQiKQogIAogIHByaW50KHAyKQogICNjb3dwbG90OjpwbG90X2dyaWQocDEsIHAyLCBuY29sID0gMSkKICAKICAKICBjb3JyX3dpbmRvdyRDb2xJbmRleCA8LSBtYXRjaChjb3JyX3dpbmRvdyRpZHhBVEFDLCB1bmlxdWUoY29ycl93aW5kb3ckaWR4QVRBQykpCiAgY29ycl93aW5kb3ckUm93SW5kZXggPC0gbWF0Y2goY29ycl93aW5kb3ckZ2VuZSwgdW5pcXVlKGNvcnJfd2luZG93JGdlbmUpKQogIAogIHAyZ19saW5rc19nZW5lX3dpbmRvdyA8LSBNYXRyaXg6OnNwYXJzZU1hdHJpeCgKICAgICAgaSA9IGNvcnJfd2luZG93JGlkeFJOQSwgCiAgICAgIGogPSBjb3JyX3dpbmRvdyRpZHhBVEFDLCAKICAgICAgeCA9IGNvcnJfd2luZG93JENvcnJlbGF0aW9uLCAKICAgICAgZGltcyA9IGMobnJvdyhleHByX21hdCksIG5yb3cocGVha19tYXQpKSwKICAgICAgZGltbmFtZXMgPSBsaXN0KHJvd25hbWVzKGV4cHJfbWF0KSxyb3duYW1lcyhwZWFrX21hdCkpCiAgICApCiAgCiAgcHJpbnQocGFzdGUwKCJUaGUgcGVhay10by1nZW5lIGxpbmtzIG1hdHJpeCwgcmVzdHJpY3RlZCB0byBhICsvLSAxMDBrYiB3aW5kb3cgYXJvdW5kIHRoZSBUU1MgaGFzIGRpbWVuc2lvbnMgIiwgc3BsaXQoZGltKHAyZ19saW5rc19nZW5lX3dpbmRvdyksIDEpKSkKICAKICBwcmludChwYXN0ZTAoIlRoZSBtYXhpbXVtIHZhbHVlIGlzOiAiLCBtYXgocDJnX2xpbmtzX2dlbmVfd2luZG93KSwgIiwgdGhlIG1pbnVtIHZhbHVlIGlzOiAiLCBtaW4ocDJnX2xpbmtzX2dlbmVfd2luZG93KSApKQogIAogIAogIAogIHAyZ19saW5rc19nZW5lX3dpbmRvdyA8LSBwMmdfbGlua3NfZ2VuZV93aW5kb3dbcm93U3VtcyhwMmdfbGlua3NfZ2VuZV93aW5kb3cpICE9IDAsIF0KICBwMmdfbGlua3NfZ2VuZV93aW5kb3cgPC0gcDJnX2xpbmtzX2dlbmVfd2luZG93WywgY29sU3VtcyhwMmdfbGlua3NfZ2VuZV93aW5kb3cpICE9IDBdCiAgCiAgcHJpbnQocGFzdGUwKCJBZnRlciByZW1vdmluZyBhbnkgcm93cyBhbmQgY29sdW1zbiB3aGljaCBkbyBub3QgY29udGFpbiBhbnkgbGlua3Mgd2UgYXJlIGxlZnQgd2l0aCAiLCBucm93KHAyZ19saW5rc19nZW5lX3dpbmRvdyksICIgZ2VuZXMgYW5kICIsIG5jb2wocDJnX2xpbmtzX2dlbmVfd2luZG93KSwgIiBwZWFrcy4iKSkKICAjIENvbXB1dGUgZ2VuZSBhY3Rpdml0eSBzY29yZXMKICBnZW5lX3dpbmRvd19zY29yZXMgPC0gZ2VuZV9hY3Rpdml0eV9zY29yZXMocGVha19tYXRfc3ViW2NvbG5hbWVzKHAyZ19saW5rc19nZW5lX3dpbmRvdyksIF0sIHAyZ19saW5rc19nZW5lX3dpbmRvdykKICBkaW0oZ2VuZV93aW5kb3dfc2NvcmVzKQoKCiAgIyAjIGNyZWF0ZSBkaXN0YW5jZSB3ZWlnaHQgbWF0cml4CiAgIyBwMmdfZHcgPC0gc3BhcnNlTWF0cml4KGkgPSBwMmdfam9pbiRpZHhSTkEsCiAgIyAgICAgICAgICAgICAgICAgICAgICAgIGogPSBwMmdfam9pbiRpZHhBVEFDLAogICMgICAgICAgICAgICAgICAgICAgICAgICB4ID0gcDJnX2pvaW4kZGlzdGFuY2Vfd2VpZ2h0LAogICMgICAgICAgICAgICAgICAgICAgICAgICBkaW1zID0gYyhkaW0oYXNzYXlzKGdlbmVfZXhwcilbWzFdXSlbMV0sCiAgIyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRpbShwZWFrX21hdClbMV0pLAogICMgICAgICAgICAgICAgICAgICAgICAgICBkaW1uYW1lcyA9IGxpc3Qocm93RGF0YShnZW5lX2V4cHIpJG5hbWUgLCAKICAjICAgICAgICAgICAgICAgICAgICAgICAgc2VxLmludChkaW0ocGVha19tYXQpWzFdKSkpCiAgIyAKICAjIAogICMgcDJnX2R3IDwtIHAyZ19kd1thcy52ZWN0b3Iocm93bmFtZXMocDJnX21hdF9zdWIpKSwgY29sbmFtZXMocDJnX21hdF9zdWIpXQogICMgCiAgIyAjIGVsZW1lbnR3aXNlIG1hdHJpeCBtdWx0aXBsaWNhdGlvbgogICMgd2VpZ2h0ZWRfcDJnX21hdCA8LSBwMmdfbWF0X3N1YiAqIHAyZ19kdwogICMgCiAgIyBwcmludChwYXN0ZShsZW5ndGgod2hpY2gocm93U3Vtcyh3ZWlnaHRlZF9wMmdfbWF0KSA9PSAwKSksICJnZW5lcyBoYXZlIG9ubHkgemVybyBjb3JyZWxhdGlvbiB2YWx1ZXMsIHNvIHdlIHdpbGwgcmVtb3ZlIHRoZW0uIikpCiAgIyB3ZWlnaHRlZF9wMmdfbWF0IDwtIHdlaWdodGVkX3AyZ19tYXRbcm93U3Vtcyh3ZWlnaHRlZF9wMmdfbWF0KSAhPSAwLCBdCiAgIyBwcmludChwYXN0ZTAoIldlIGFyZSBsZWZ0IHdpdGggIiwgZGltKHdlaWdodGVkX3AyZ19tYXQpWzFdLCAiIGdlbmVzIikpCiAgIyAKICAjICMgY29tcHV0ZSBnZW5lIGFjdGl2aXR5IHNjb3JlcyBiYXNlZCBvbiBkaXN0YW5jZS13ZWlnaHRlZCBwZWFrMmdlbmUgbWF0cml4CiAgIyB3ZWlnaHRlZF9zY29yZXMgPC0gZ2VuZV9hY3Rpdml0eV9zY29yZXMocGVha19tYXRfc3ViLCB3ZWlnaHRlZF9wMmdfbWF0KQogIAogIHJldHVybihnZW5lX3dpbmRvd19zY29yZXMpIAp9CmBgYAoKYGBge3J9CmdlbmVfd2luZG93X3Njb3JlcyA8LSBjb21wdXRlX2dlbmVfd2luZG93X3Njb3JlKAogIHAyZ19tYXRfc3ViID0gcDJnX21hdF9zdWIsIAogIHdlaWdodCA9IDUwMDAwLAogIHBlYWtfbWF0ID0gcGVha19tYXQsIAogIGxpbmtzID0gbGlua3MsIAogIHAyZ19vcmlnaW5hbCA9IHAyZywgCiAgZ2VuZV9leHByID0gZ2VuZV9leHByKQpgYGAKCmBgYHtyLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD01fQp3ZWlnaHRlZF9zY29yZXNfYWdnIDwtIGtubl9hZ2dyZWdhdGVzKGdlbmVfd2luZG93X3Njb3JlcywgY2VsbF9hZ2dfbGlzdCkKd2VpZ2h0ZWRfa25uX2NvcnIgPC0gcm93d2lzZV9jb3JyZWxhdGlvbnMocm5hX2FnZywgd2VpZ2h0ZWRfc2NvcmVzX2FnZywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIlAyZyBsaW5rcyB3aXRoaW4gZ2VuZSB3aW5kb3ciKQp3ZWlnaHRlZF9rbm5fY29ycltbMl1dCgpnZ3Bsb3QoKSArIGdlb21fZGVuc2l0eV8yZF9maWxsZWQoYWVzKHggPSB3ZWlnaHRlZF9rbm5fY29ycltbMV1dLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5ID0gYXJjaHJfa25uW1sxXV1bbmFtZXMod2VpZ2h0ZWRfa25uX2NvcnJbWzFdXSldKSwgYWxwaGEgPSAuNSkgKwpnZW9tX3BvaW50KGFlcyh4ID0gd2VpZ2h0ZWRfa25uX2NvcnJbWzFdXSwgeSA9IGFyY2hyX2tubltbMV1dW25hbWVzKHdlaWdodGVkX2tubl9jb3JyW1sxXV0pXSkpICsKZ2VvbV9saW5lKGFlcyh4ID0gd2VpZ2h0ZWRfa25uX2NvcnJbWzFdXSwgeSA9IHdlaWdodGVkX2tubl9jb3JyW1sxXV0pLCBjb2wgPSAicmVkIikgKwp0aGVtZShsZWdlbmQucG9zaXRpb24gPSAiTm9uZSIpICArCmxhYnMoeCA9ICJDb3JyZWxhdGlvbiBiZXR3ZWVuIGdlbmUgZXhwcmVzc2lvbiBhbmQgcDJnIGFjdGl2aXR5IHNjb3JlcyIsCiAgICAgIHRpdGxlID0gIlBlYWstdG8tZ2VuZSBsaW5rcyBhcmUgcmVzdHJpY3RlZCB0byBhIGdlbmUgd2luZG93IG9mICsvLSAxMDBrYiBhcm91bmQgVFNTIiwKICAgICAgeSA9ICJDb3JyZWxhdGlvbiBiZXR3ZWVuIGdlbmUgZXhwcmVzc2lvbiBhbmQgQXJjaFIgZ2VuZSBhY3Rpdml0eSBzY29yZXMiKQoKCgpgYGAKCgoKCiMgRWZmZWN0IG9mIHVzaW5nIGRpZmZlcmVudCBkaXN0YW5jZSBkZWNheSByYXRlcyAKCkhvdyBkb2VzIHRoZSBkaXN0YW5jZSB3ZWlnaHQgZGlzdHJpYnV0aW9uIGNoYW5nZSB3aXRoIGRpZmZlcmVudCBkZWNheSByYXRlcz8KCkhlcmUsIHdlIHVzZSB0aGUgZm9ybXVsYSAkZV57XGZyYWN7LWFicyhkaXN0YW5jZSl9e2N9fSQgd2l0aCBkaWZmZXJlbiBkZWNheSByYXRlcwokYyBcaW4gXHs1MDAwLCA1MDAwMCwgNTAwMDAwLCA1MDAwMDAwXH0kLiBBZGRpdGlvbmFsbHksIHdlIHVzZSBvbmx5IHBlYWtzIHdoaWNoIApvdmVybGFwIHdpdGggYSArLy0gMTAwMGtiIHdpbmRvdyBmcm9tIHRoZSBUU1MuCgpgYGB7ciwgZmlnLndpZHRoPTEwLGZpZy5oZWlnaHQ9OX0KbW9kZWxfbGlzdCA8LSBjKCJleHAoLWFicyhkaXN0YW5jZSkvNTAwMCkiLCAiZXhwKC1hYnMoZGlzdGFuY2UpLzUwMDAwKSIsCiAgICAgICAgICAgICAgICAiZXhwKC1hYnMoZGlzdGFuY2UpLzUwMDAwMCkiLCAiZXhwKC1hYnMoZGlzdGFuY2UpLzUwMDAwMDApIikKCgoKYXRhY19ncmFuZ2VzIDwtIG1ldGFkYXRhKHAyZylbWzFdXQojcm5hX2dyYW5nZXMgPC0gbWV0YWRhdGEocDJnX29yaWdpbmFsKVtbMl1dCmdlbmVfYW5ubyA8LSByb3dEYXRhKGdlbmVfZXhwcikKCiMgY3JlYXRlIGdlbmUgYW5ub3RhdGlvbnMgd2l0aCBzdGFydCBjb29yZGluYXRlIG9mIGVhY2ggZ2VuZQojIHN1YnNldCB0byBjb250YWluIG9ubHkgZ2VuZXMgd2hpY2ggYXJlIGluY2x1ZGVkIGluIG91ciBwZWFrMmdlbmUgbWF0cml4CmdlbmVfYW5ubyA8LSBnZW5lX2Fubm8gJT4lIGFzLmRhdGEuZnJhbWUoKSAlPiUKICBtdXRhdGUoaWR4Uk5BID0gc2VxKG5yb3coLikpKSAlPiUgCiAgZmlsdGVyKG5hbWUgJWluJSByb3duYW1lcyhwMmdfbWF0X3N1YikpICU+JQogIG11dGF0ZShzdHJhbmQgPSBpZmVsc2Uoc3RyYW5kID09IDEsICIrIiwgIi0iKSkgJT4lCiAgbXV0YXRlKHN0YXJ0X2Nvb3JkID0gaWZlbHNlKHN0cmFuZCA9PSAiKyIsIHN0YXJ0LCBlbmQpKSAlPiUgCiAgcmVuYW1lKGdlbmUgPSBuYW1lKSAjJT4lIEdSYW5nZXMoKQoKI2dlbmVSZWdpb25zIDwtIGdlbmVfYW5ubyAlPiUgR1JhbmdlcygpCmdlbmVfcmVnaW9ucyAgPC0gcmVzaXplKGdlbmVfYW5ubyAlPiUgR1JhbmdlcygpLCB3aWR0aCA9IDEpCmV4dGVuZGVkR2VuZVJlZ2lvbiA8LSAoc3VwcHJlc3NXYXJuaW5ncyhleHRlbmRHUihnZW5lX3JlZ2lvbnMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB1cHN0cmVhbSA9IDEwMDAwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRvd25zdHJlYW0gPSAxMDAwMDApKSkKIyBzdWJzZXQgYXRhYyBncmFuZ2VzICYgZ2V0IG1pZGRsZSBvZiBlYWNoIHBlYWsKcG9zX2F0YWNfZ3JhbmdlcyA8LSBhdGFjX2dyYW5nZXMgICU+JSAKICBhcy5kYXRhLmZyYW1lKCkgJT4lCiAgbXV0YXRlKGlkeEFUQUMgPSBzZXEobnJvdyguKSkpICU+JSAKICAjIGdyb3VwX2J5KHNlcW5hbWVzKSAlPiUKICAjIG11dGF0ZShpZHggPSBzZXFfYWxvbmcoc2VxbmFtZXMpKSAlPiUgCiAgIyB1bmdyb3VwICU+JQogICN0aWR5cjo6dW5pdGUoY2hyX2lkeCwgc2VxbmFtZXMsIGlkeCwgcmVtb3ZlID0gRkFMU0UsIHNlcCA9ICJfIikgJT4lIAogIGZpbHRlcihpZHhBVEFDICVpbiUgY29sbmFtZXMocDJnX21hdF9zdWIpKSAlPiUgCiAgbXV0YXRlKG1pZGRsZSA9IHN0YXJ0ICsgMzAwKSAjJT4lIEdSYW5nZXMoKSAKCiNUT0RPOiBGaWx0ZXIgZm9yIGdlbmVzIQpzdG9waWZub3QobGVuZ3RoKHVuaXF1ZShsaW5rcyRpZHhBVEFDKSkgPT0gZGltKHBvc19hdGFjX2dyYW5nZXMpW1sxXV0pCnN0b3BpZm5vdChsZW5ndGgodW5pcXVlKGxpbmtzJGlkeFJOQSkpID09IGRpbShnZW5lX2Fubm8pW1sxXV0pCiNwMmdfZmlsdCA8LSBwMmdfb3JpZ2luYWwgJT4lIGFzLmRhdGEuZnJhbWUoKSAlPiUgZmlsdGVyKGdlbmUgJWluJSByb3duYW1lcyhwMmdfbWF0KSkKCgogICMgZmluZCBvdmVybGFwcGluZyBwZWFrcyBhbmQgZ2VuZSB3aW5kb3cgaW4gY2hyb21vc29tZS1hd2FyZSBmYXNoaW9uCnRtcCA8LSBzdXBwcmVzc1dhcm5pbmdzKGZpbmRPdmVybGFwcyhleHRlbmRlZEdlbmVSZWdpb24sIHBvc19hdGFjX2dyYW5nZXMgJT4lIEdSYW5nZXMoKSkpCgpwcmludChwYXN0ZTAoIk91dCBvZiAiLCBzdWJqZWN0TGVuZ3RoKHRtcCksICIgcGVha3Mgb25seSAiLAogICAgICAgICAgICAgbGVuZ3RoKHVuaXF1ZShzdWJqZWN0SGl0cyh0bXApKSksICIgcGVha3MgYXJlIGZvdW5kIHdpdGhpbiBnZW5lIHdpbmRvdyBvZiAyMDBrYi4iKSkKCgojIyMgc29tZSBwbG90cwpwcmludCh0bXAgJT4lIGFzLmRhdGEuZnJhbWUoKSAlPiUgCiAgICAgICBncm91cF9ieShxdWVyeUhpdHMpICU+JSAjIGdlbmUgcmVnaW9uCiAgICAgICBzdW1tYXJpemUobiA9IG4oKSkgJT4lICMgZ2V0IG51bWJlciBvZiBwZWFrcyBvdmVybGFwcGluZyB3aXRoIGEgZ2VuZSByZWdpb24KICAgICAgIGdncGxvdCgpICsgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSBuKSwgYmlucyA9IDEwMCwgZmlsbD0iIzY5YjNhMiIpICsKICAgICAgIGxhYnModGl0bGUgPSAibnVtYmVyIG9mIHBlYWtzIHBlciBnZW5lIHJlZ2lvbiBvZiBzaXplICsvLSAxMDBrYiBmcm9tIFRTUyIsCiAgICAgICAgICAgeCA9ICJudW1iZXIgb2YgcGVha3Mgd2l0aGluIHdpbmRvdyIpKQogIAogIAogIAogICMgY29tYmluZSB0aGUgdGhyZWUgZGF0YWZyYW1lcwogIHAyZ19qb2luIDwtIGxlZnRfam9pbihsaW5rcywgYXMuZGF0YS5mcmFtZShwb3NfYXRhY19ncmFuZ2VzKSwKICAgICAgICAgICAgICAgICAgICAgICAgYnkgPSAiaWR4QVRBQyIpCiAgcDJnX2pvaW4gPC0gbGVmdF9qb2luKHAyZ19qb2luLCBhcy5kYXRhLmZyYW1lKGdlbmVfYW5ubyksCiAgICAgICAgICAgICAgICAgICAgICAgIGJ5ID0gImlkeFJOQSIsIHN1ZmZpeCA9IGMoIi5hdGFjIiwgIi5ybmEiKSkKCmZvciAobW9kZWwgaW4gbW9kZWxfbGlzdCl7IAojIGNvbXB1dGUgZGlzdGFuY2UgYW5kIGRpc3RhbmNlIHdlaWdodHMgCiAgcDJnX2pvaW4gPC0gcDJnX2pvaW4gJT4lIAogICAgbXV0YXRlKGRpc3RhbmNlID0gYWJzKHN0YXJ0X2Nvb3JkIC0gbWlkZGxlKSkgJT4lCiAgICBtdXRhdGUoZGlzdGFuY2Vfd2VpZ2h0ID0gZXZhbChwYXJzZSh0ZXh0PW1vZGVsKSkpCiAgCiAgcDEgPC0gcDJnX2pvaW4gJT4lIGdncGxvdCgpICsKICAgIGdlb21faGlzdG9ncmFtKGFlcyh4ID0gZGlzdGFuY2UpLCBiaW5zID0gMjAwLCBmaWxsPSIjNjliM2EyIikgKwogICAgbGFicyh0aXRsZSA9ICJEaXN0YW5jZSBiZXR3ZWVuIHBlYWtzIGFuZCBnZW5lcyIsIHggPSAiZGlzdGFuY2UiKSArCiAgICBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQgID0gNTAwMCwgY29sb3IgPSAicmVkIikgKwogICAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ICA9IDI1MDAwMCwgY29sb3IgPSAib3JhbmdlIikKICAKICBwMiA8LSBwMmdfam9pbiAlPiUgZ2dwbG90KCkgKwogICAgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSAoZGlzdGFuY2Vfd2VpZ2h0KSksIGJpbnMgPSAyMDAsIGZpbGw9IiM2OWIzYTIiKSArCiAgICBzY2FsZV95X2xvZzEwKCkgKwogICAgbGFicyh0aXRsZSA9IHBhc3RlMCgiRGlzdGFuY2UgV2VpZ2h0cyBjb21wdXRlZCB1c2luZyAiLCBtb2RlbCksCiAgICAgICAgIHggPSAiZGlzdGFuY2Ugd2VpZ2h0cyIsIHkgPSAibG9nMTAoY291bnRzKSIpCiAgCiAgcHJpbnQoY293cGxvdDo6cGxvdF9ncmlkKHAxLCBwMiwgbmNvbCA9IDIpKQoKfQogICMgUmVsYXRpb25zaGlwIGJldHdlZW4gZGlzdGFuY2UgYW5kIGNvcnJlbGF0aW9uIHZhbHVlCiMgcDMgPC0gcDJnX2pvaW4gJT4lIGdncGxvdCgpICsKIyAgIGdlb21fcG9pbnQoYWVzKHggPSBDb3JyZWxhdGlvbiwgeSA9IGRpc3RhbmNlKSkgKwojICAgbGFicyh0aXRsZSA9ICJEaXN0YW5jZSB2cy4gY29ycmVsYXRpb24gYmV0d2VlbiBwZWFrcyBhbmQgZ2VuZXMiLAojICAgICAgICB4ID0gIkNvcnJlbGF0aW9uIGJldHdlZW4gcGVhayBhbmQgZ2VuZSIsIAojICAgICAgICB5ID0gIkRpc3RhbmNlIGJldHdlZW4gcGVhayBhbmQgZ2VuZSIpCiMgCiMgCiMgcDQgPC0gcDJnX2pvaW4gJT4lIGdncGxvdCgpICsKIyAgIGdlb21fcG9pbnQoYWVzKHggPSBDb3JyZWxhdGlvbiwgeSA9IGRpc3RhbmNlX3dlaWdodCkpICsKIyAgIGxhYnModGl0bGUgPSAiRGlzdGFuY2UgdnMuIGNvcnJlbGF0aW9uIGJldHdlZW4gcGVha3MgYW5kIGdlbmVzIiwKIyAgICAgICAgeCA9ICJDb3JyZWxhdGlvbiBiZXR3ZWVuIHBlYWsgYW5kIGdlbmUiLCAKIyAgICAgICAgeSA9ICJEaXN0YW5jZSB3ZWlnaHRzIGJldHdlZW4gcGVhayBhbmQgZ2VuZSIpCgoKI2Nvd3Bsb3Q6OnBsb3RfZ3JpZChwMSwgcDIsIG5jb2wgPSAxKQoKYGBgCgoKIyMjIFJlbGF0aW9uc2hpcCBiZXR3ZWVuIGRpc3RhbmNlIGFuZCBjb3JyZWxhdGlvbiB2YWx1ZXMKCmBgYHtyLGZpZy53aWR0aD0xNX0KCiMgT2xvdCByZWxhdGlvbnNoaXAgYmV0d2VlbiBkaXN0YW5jZSBhbmQgY29ycmVsYXRpb24gYXMgZGVuc2l0eSBwbG90cwpwMSA8LSBwMmdfam9pbiAlPiUgZ2dwbG90KCkgKyAKICBnZW9tX2RlbnNpdHlfMmRfZmlsbGVkKGFlcyh4ID0gQ29ycmVsYXRpb24sIHkgPSBkaXN0YW5jZSkpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAiTm9uZSIpICsKICBsYWJzKHRpdGxlID0gIlJlbGF0aW9uc2hpcCBiZXR3ZWVuIGRpc3RhbmNlIGFuZCBjb3JyZWxhdGlvbiIpCgpwMiA8LSBwMmdfam9pbiAlPiUKICBmaWx0ZXIoQ29ycmVsYXRpb24gPiAwLjMpICU+JSAKICBnZ3Bsb3QoKSArIAogIGdlb21fZGVuc2l0eV8yZF9maWxsZWQoYWVzKHggPSBDb3JyZWxhdGlvbiwgeSA9IGRpc3RhbmNlKSkgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJOb25lIikgKwogIGxhYnModGl0bGUgPSAiUmVsYXRpb25zaGlwIGJldHdlZW4gZGlzdGFuY2UgYW5kIGNvcnJlbGF0aW9uIikKCnAzIDwtIHAyZ19qb2luICU+JQogIGZpbHRlcihDb3JyZWxhdGlvbiA+IDAuNikgJT4lIAogIGdncGxvdCgpICsgCiAgZ2VvbV9kZW5zaXR5XzJkX2ZpbGxlZChhZXMoeCA9IENvcnJlbGF0aW9uLCB5ID0gZGlzdGFuY2UpKSArCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIk5vbmUiKSArCiAgbGFicyh0aXRsZSA9ICJSZWxhdGlvbnNoaXAgYmV0d2VlbiBkaXN0YW5jZSBhbmQgY29ycmVsYXRpb24iKQoKY293cGxvdDo6cGxvdF9ncmlkKHAxLCBwMiwgcDMsIG5jb2wgPSAyKQpgYGAKCgpgYGB7ciwgZmlnLndpZHRoPTEwfQpwMmdfam9pbiAlPiUgIAogIG11dGF0ZShiaW49Y3V0X3dpZHRoKGRpc3RhbmNlLCB3aWR0aD0xMDAwMCwgYm91bmRhcnk9MCkpICU+JQogIGZpbHRlcihkaXN0YW5jZSA8IDI1MDAwMCkgJT4lIAogIGdncGxvdCgpICsKICBnZW9tX2JveHBsb3QoYWVzKHggPSBiaW4sIHkgPSBDb3JyZWxhdGlvbiksIGZpbGw9IiM2OWIzYTIiKSArCiAgI2dlb21fdmxpbmUoeGludGVyY2VwdCAgPSAyNTAwMDAsIGNvbG9yID0gInJlZCIpICsKICBsYWJzKHRpdGxlID0gIlJlbGF0aW9uc2hpcCBiZXR3ZWVuIGRpc3RhbmNlIGFuZCBjb3JyZWxhdGlvbiBvZiBwMmcgbGlua3MsIDEwMGtiIGJpbnMiLAogICAgICAgeCA9ICJEaXN0YW5jZSBiZXR3ZWVuIHBlYWtzIGFuZCBnZW5lcyB3aXRoaW4gMjUwa2IiLCB5ID0gIkNvcnJlbGF0aW9uIikgKyAKICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDkwLCB2anVzdCA9IDAuNSwgaGp1c3Q9MSkpCmBgYAoKYGBge3IsIGZpZy53aWR0aD0yMiwgZmlnLmhlaWdodD0xNX0KCnAxIDwtIHAyZ19qb2luICU+JSAgCiAgbXV0YXRlKGJpbj1jdXRfd2lkdGgoZGlzdGFuY2UsIHdpZHRoPTEwMDAwMCwgYm91bmRhcnk9MCkpICU+JQogIGZpbHRlcihkaXN0YW5jZSA8IDEwMDAwMDAwICYgQ29ycmVsYXRpb24gPiAwLjUpICU+JSAKICBnZ3Bsb3QoKSArCiAgZ2VvbV9ib3hwbG90KGFlcyh4ID0gYmluLCB5ID0gQ29ycmVsYXRpb24pLCBmaWxsPSIjNjliM2EyIikgKwogIGxhYnModGl0bGUgPSAiUmVsYXRpb25zaGlwIGJldHdlZW4gZGlzdGFuY2UgYW5kIGNvcnJlbGF0aW9uIG9mIHAyZyBsaW5rcywgMTAwa2IgYmlucyIsCiAgICAgICB4ID0gIkRpc3RhbmNlIDwgMWVeNyBicCIsIHkgPSAiQ29ycmVsYXRpb24gPiAwLjUiKSArIAogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIHZqdXN0ID0gMC41LCBoanVzdD0xKSkKCnAyIDwtIHAyZ19qb2luICU+JSAgCiAgbXV0YXRlKGJpbj1jdXRfd2lkdGgoZGlzdGFuY2UsIHdpZHRoPTEwMDAwMCwgYm91bmRhcnk9MCkpICU+JQogIGZpbHRlcihkaXN0YW5jZSA8IDEwMDAwMDAwICYgQ29ycmVsYXRpb24gPiAwLjgpICU+JSAKICBnZ3Bsb3QoKSArCiAgZ2VvbV9ib3hwbG90KGFlcyh4ID0gYmluLCB5ID0gQ29ycmVsYXRpb24pLCBmaWxsPSIjNjliM2EyIikgKwogIGxhYnModGl0bGUgPSAiUmVsYXRpb25zaGlwIGJldHdlZW4gZGlzdGFuY2UgYW5kIGNvcnJlbGF0aW9uIG9mIHAyZyBsaW5rcywgMTAwa2IgYmlucyIsCiAgICAgICB4ID0gIkRpc3RhbmNlIDwgMWVeNyBicCIsIHkgPSAiQ29ycmVsYXRpb24gPiAwLjgiKSArIAogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIHZqdXN0ID0gMC41LCBoanVzdD0xKSkKCnAzIDwtIHAyZ19qb2luICU+JSAgCiAgbXV0YXRlKGJpbj1jdXRfd2lkdGgoZGlzdGFuY2UsIHdpZHRoPTEwMDAwMCwgYm91bmRhcnk9MCkpICU+JQogIGZpbHRlcihkaXN0YW5jZSA8IDEwMDAwMDAwICYgQ29ycmVsYXRpb24gPCAwLjUpICU+JSAKICBnZ3Bsb3QoKSArCiAgZ2VvbV9ib3hwbG90KGFlcyh4ID0gYmluLCB5ID0gQ29ycmVsYXRpb24pLCBmaWxsPSIjNjliM2EyIikgKwogIGxhYnModGl0bGUgPSAiUmVsYXRpb25zaGlwIGJldHdlZW4gZGlzdGFuY2UgYW5kIGNvcnJlbGF0aW9uIG9mIHAyZyBsaW5rcywgMTAwa2IgYmlucyIsCiAgICAgICB4ID0gIkRpc3RhbmNlIDwgMWVeNyBicCIsIHkgPSAiQ29ycmVsYXRpb24gPCAwLjUiKSArIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIHZqdXN0ID0gMC41LCBoanVzdD0xKSkKCgoKcDQgPC0gcDJnX2pvaW4gJT4lICAKICBtdXRhdGUoYmluPWN1dF93aWR0aChkaXN0YW5jZSwgd2lkdGg9MTAwMCwgYm91bmRhcnk9MCkpICU+JQogIGZpbHRlcihkaXN0YW5jZSA8IDEwMDAwMCAmIENvcnJlbGF0aW9uID4gMC41KSAlPiUgCiAgZ2dwbG90KCkgKwogIGdlb21fYm94cGxvdChhZXMoeCA9IGJpbiwgeSA9IENvcnJlbGF0aW9uKSwgZmlsbD0iIzY5YjNhMiIpICsKICBsYWJzKHRpdGxlID0gIlJlbGF0aW9uc2hpcCBiZXR3ZWVuIGRpc3RhbmNlIGFuZCBjb3JyZWxhdGlvbiBvZiBwMmcgbGlua3MsIDFrYiBiaW5zIiwKICAgICAgIHggPSAiRGlzdGFuY2UgPCAxMDBrYiIsIHkgPSAiQ29ycmVsYXRpb24gPiAwLjUiKSArIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIHZqdXN0ID0gMC41LCBoanVzdD0xKSkKCgpjb3dwbG90OjpwbG90X2dyaWQocDEsIHAyLCBwMywgcDQsIG5jb2wgPSAyKQpgYGAKCgoKVHJ5IGRpc3RhbmNlIHdlaWdodHMKCgpgYGB7cn0Kcm5hX2tubiA8LSByZWFkUkRTKCIxMV9hZGRlZF9SaWNhcmRzX3BlYWtzL1BlYWsyR2VuZUxpbmtzL3NlUk5BLUdyb3VwLUtOTi5yZHMiKQojcm5hX2FnZ19tYXQgPC0gYXNzYXlzKHJuYV9rbm4pW1sxXV0KI3Jvd25hbWVzKHJuYV9hZ2dfbWF0KSA8LSByb3dEYXRhKHJuYV9rbm4pJG5hbWUKCmNlbGxfYWdnX2xpc3QgPC0gbWV0YWRhdGEocm5hX2tubilbWzFdXQoKCmtubl9hZ2dyZWdhdGVzIDwtIGZ1bmN0aW9uKG1hdHJpeCwgY2VsbF9hZ2dfbGlzdCl7CiAgIyBlbXB0eSBtYXRyaXggdG8gc3RvcmUgYWdncmVnYXRlcwogIGFnZyA8LSBtYXRyaXgoZGF0YSA9IDAsCiAgICAgICAgICAgICAgICBucm93ID0gZGltKG1hdHJpeClbMV0sCiAgICAgICAgICAgICAgICBuY29sID0gbGVuZ3RoKGNlbGxfYWdnX2xpc3QpLAogICAgICAgICAgICAgICAgZGltbmFtZXMgPSBsaXN0KHJvd25hbWVzKG1hdHJpeCksIE5VTEwpKQogIAogIGZvciAoaSBpbiBzZXEuaW50KGxlbmd0aChjZWxsX2FnZ19saXN0KSkpIHsKICAgIGFnZ1ssIGldIDwtIHJvd1N1bXMobWF0cml4WywgY2VsbF9hZ2dfbGlzdFtbaV1dXSkKICB9CiAgcmV0dXJuKGFnZykKfQoKCnJuYV9hZ2cgPC0ga25uX2FnZ3JlZ2F0ZXMoZXhwcl9tYXRfc3ViLCBjZWxsX2FnZ19saXN0KQphcmNocl9rbm4gPC0gYXJjaHJfc2NvcmVzX21hdFthcy52ZWN0b3Iocm93bmFtZXMoYWdnX3AyZ19rbm4pKSxdCmFnZ19hcmNocl9rbm4gPC0ga25uX2FnZ3JlZ2F0ZXMoYXJjaHJfa25uLCBjZWxsX2FnZ19saXN0KQoKYWdnX3AyZ19rbm4gPC0ga25uX2FnZ3JlZ2F0ZXMocDJnX3Njb3JlcywgY2VsbF9hZ2dfbGlzdCkKYWdnX2Rpc3QgPC0ga25uX2FnZ3JlZ2F0ZXMod2VpZ2h0ZWRfc2NvcmVzLCBjZWxsX2FnZ19saXN0KQpgYGAKCgpgYGB7ciwgZmlnLndpZHRoPTEwfQphcmNocl9rbm4gPC0gcm93d2lzZV9jb3JyZWxhdGlvbnMocm5hX2FnZywgYWdnX2FyY2hyX2tubiwgIkFyY2hyIGdlbmUgYWN0aXZpdHkgc2NvcmVzIikKcDJnX2tubiA8LSByb3d3aXNlX2NvcnJlbGF0aW9ucyhybmFfYWdnLCBhZ2dfcDJnX2tubiwgIlBlYWstdG8tZ2VuZSBsaW5rcyBhY3Rpdml0eSBzY29yZXMiKQpkaXN0X2tubiA8LSByb3d3aXNlX2NvcnJlbGF0aW9ucyhybmFfYWdnLCBhZ2dfZGlzdCwgIlBlYWstdG9fZ2VuZSBsaW5rcyBhY3Rpdml0eSBzY29yZXMgd2VpZ2h0ZWQgYnkgZGlzdGFuY2UiKQpjb3dwbG90OjpwbG90X2dyaWQoYXJjaHJfa25uW1syXV0sIHAyZ19rbm5bWzJdXSwgZGlzdF9rbm5bWzJdXSwgbmNvbCA9IDIpCgpwMSA8LSBnZ3Bsb3QoKSArIGdlb21fZGVuc2l0eV8yZF9maWxsZWQoYWVzKHggPSBwMmdfa25uW1sxXV0sIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHkgPSBhcmNocl9rbm5bWzFdXSksIGFscGhhID0gLjUpICsKICBnZW9tX3BvaW50KGFlcyh4ID0gcDJnX2tubltbMV1dLCB5ID0gYXJjaHJfa25uW1sxXV0pKSArCiAgZ2VvbV9saW5lKGFlcyh4ID0gcDJnX2tubltbMV1dLCB5ID0gcDJnX2tubltbMV1dKSwgY29sID0gInJlZCIpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAiTm9uZSIpIAogIAogIApwMiA8LSBnZ3Bsb3QoKSArIGdlb21fZGVuc2l0eV8yZF9maWxsZWQoYWVzKHggPSBkaXN0X2tubltbMV1dLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5ID0gYXJjaHJfa25uW1sxXV0pLCBhbHBoYSA9IC41KSArCiAgZ2VvbV9wb2ludChhZXMoeCA9IGRpc3Rfa25uW1sxXV0sIHkgPSBhcmNocl9rbm5bWzFdXSkpICsKICBnZW9tX2xpbmUoYWVzKHggPSBkaXN0X2tubltbMV1dLCB5ID0gZGlzdF9rbm5bWzFdXSksIGNvbCA9ICJyZWQiKSArCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIk5vbmUiKSAKCmNvd3Bsb3Q6OnBsb3RfZ3JpZChwMSwgcDIsIG5jb2wgPSAyKQpgYGAKCgoKCiMgRXhhbXBsZSByZXN0cmljdGluZyBsaW5rcyB0byBHZW5lIHdpbmRvdyAKCkxldHMgY2hlY2sgd2hldGhlciB0aGUgcmVzdWx0cyB3ZSBnb3QgcHJldmlvdXNseSBhbHNvIHlpZWxkIGhpZ2ggY29ycmVsYXRpb25zLiBJbgp0aGlzIGNhc2UsIHVzaW5nIGFsbCBwMmcgbGlua3MgYWNyb3NzIHRoZSBlbnRpcmUgY2hyb21zb21lLCB3ZSBjb21wdXRlZApnZW5lIGFjdGl2aXR5IHNjb3JlcywgYnV0IHJlc3RyaWN0aW5nIGxpbmtzIHRvIHdpdGhpbiBhIGdlbmUgd2luZG93IG9mICsvLSAxMDBrYi4KCmBgYHtyfQoKdGVzdCA8LSByZWFkSDVBRCgianVweXRlcl9ub3RlYm9va3MvcDJnX2dlbmVfYWN0aXZpdHlfc2NvcmVzL2dlbmVfd2luZG93X3Njb3Jlc2dlbmVfd2luZG93X3Njb3JlcyIpCgpwMmdfc2NvcmVzIDwtIGFzc2F5cyh0ZXN0KVtbMV1dCgojIGNwX25hbWVzIDwtIGNvbG5hbWVzKGNvbERhdGEoZ2VuZV9leHByKSkKIyBjcF9uYW1lc1syMF0gPC0gImNlbGx0eXBlcyIKIyBjb2xuYW1lcyhjb2xEYXRhKGdlbmVfZXhwcikpIDwtIGNwX25hbWVzCgpyb3duYW1lcyhleHByX21hdCkgPC0gcm93RGF0YShnZW5lX2V4cHIpJG5hbWUKZ2VuZXMgPC0gZXhwcl9tYXRbYXMudmVjdG9yKHJvd25hbWVzKHAyZ19zY29yZXMpKSwgXQoKc3RvcGlmbm90KGFueShyb3duYW1lcyhnZW5lcykgPT0gcm93bmFtZXMocDJnX3Njb3JlcykpKQoKIyBjcmVhdGUgbWF0cml4IHRvIHN0b3JlIGFnZ3JlZ2F0ZXMKZXhwcl9hZ2cgPC0gbWF0cml4KGRhdGEgPSAwLCAKICAgICAgICAgICAgICAgICAgIG5yb3cgPSBkaW0oZ2VuZXMpWzFdLAogICAgICAgICAgICAgICAgICAgbmNvbCA9IGxlbmd0aCh1bmlxdWUoY29sRGF0YShnZW5lX2V4cHIpJGNlbGx0eXBlcykpLAogICAgICAgICAgICAgICAgICAgZGltbmFtZXMgID0gbGlzdChyb3duYW1lcyhwMmdfc2NvcmVzKSwKICAgICAgICAgICAgICAgICAgIHVuaXF1ZShjb2xEYXRhKGdlbmVfZXhwcikkY2VsbHR5cGVzKSkpCgoKIyBmaWxsIG1hdHJpeApmb3IgKGNlbGx0eXBlIGluIHVuaXF1ZShjb2xEYXRhKGdlbmVfZXhwcikkY2VsbHR5cGVzKSl7CiAgYmFyY29kZXMgPC0gcm93bmFtZXMoY29sRGF0YShnZW5lX2V4cHIpICU+JSAKICAgICAgICAgICAgICAgICAgICAgICAgIGFzLmRhdGEuZnJhbWUoKSAlPiUgCiAgICAgICAgICAgICAgICAgICAgICAgICBmaWx0ZXIoY2VsbHR5cGVzID09IGNlbGx0eXBlKSkKICBleHByX2FnZ1ssIGNlbGx0eXBlXSA8LSByb3dTdW1zKGdlbmVzWywgYmFyY29kZXNdKQp9CgoKCnAyZ19zY29yZV9hZ2cgPC0gbWF0cml4KGRhdGEgPSAwLCAKICAgICAgICAgICAgICAgICAgICAgICAgbnJvdyA9IGRpbShwMmdfc2NvcmVzKVsxXSwKICAgICAgICAgICAgICAgICAgICAgICAgbmNvbCA9IGxlbmd0aCh1bmlxdWUoY29sRGF0YShnZW5lX2V4cHIpJGNlbGx0eXBlcykpLAogICAgICAgICAgICAgICAgICAgICAgICBkaW1uYW1lcyA9IGxpc3Qocm93bmFtZXMocDJnX3Njb3JlcyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB1bmlxdWUoY29sRGF0YShnZW5lX2V4cHIpJGNlbGx0eXBlcykpKQoKZm9yIChjZWxsdHlwZSBpbiB1bmlxdWUoY29sRGF0YShnZW5lX2V4cHIpJGNlbGx0eXBlcykpewogIGJhcmNvZGVzIDwtIHJvd25hbWVzKGNvbERhdGEoZ2VuZV9leHByKSAlPiUgCiAgICAgICAgICAgICAgICAgICAgICAgICBhcy5kYXRhLmZyYW1lKCkgJT4lIAogICAgICAgICAgICAgICAgICAgICAgICAgZmlsdGVyKGNlbGx0eXBlcyA9PSBjZWxsdHlwZSkpCiAgcDJnX3Njb3JlX2FnZ1ssIGNlbGx0eXBlXSA8LSByb3dTdW1zKHAyZ19zY29yZXNbLCBiYXJjb2Rlc10pCn0KCmBgYAoKCgpDb3JyZWxhdGlvbnMgYmV0d2VlbiBhZ2dyZWdhdGVkIGdlbmUgZXhwcmVzc2lvbiBhbmQgYWdncmVnYXRlZCBwMmcgc2NvcmVzOgoKYGBge3J9CmNvcnJlbGF0aW9uc19nZW5lX3dpbmRvdyA9IGMoKQpmb3IgKGkgaW4gc2VxLmludChkaW0ocDJnX3Njb3JlX2FnZylbMV0pKXsKICByb3dhIDwtIGV4cHJfYWdnW2ksIF0KICByb3dhIDwtIHJvd2EgLSBtZWFuKHJvd2EpCiAgcm93YSA8LSByb3dhIC8gc2Qocm93YSkKICAKICByb3diIDwtIHAyZ19zY29yZV9hZ2dbaSwgXQogIHJvd2IgPC0gcm93YiAtIG1lYW4ocm93YikKICByb3diIDwtIHJvd2IgLyBzZChyb3diKQogIAogIGNvcnJfdmFsdWUgPSBtZWFuKHJvd2EgKiByb3diKQogIGNvcnJlbGF0aW9uc19nZW5lX3dpbmRvdyA8LSBjKGNvcnJlbGF0aW9uc19nZW5lX3dpbmRvdywgY29ycl92YWx1ZSkKfSAKbmFtZXMoY29ycmVsYXRpb25zX2dlbmVfd2luZG93KSA8LSByb3duYW1lcyhwMmdfc2NvcmVfYWdnKQoKCmdncGxvdCgpICsgZ2VvbV9oaXN0b2dyYW0oYWVzKHggPSBjb3JyZWxhdGlvbnNfZ2VuZV93aW5kb3cpLCBiaW5zID0gMjAwKSArCiAgbGFicyh0aXRsZSA9ICJHZW5lIGFjdGl2aXR5IHNjb3JlcyBjb21wdXRlZCBiYXNlZCBvbiBwMmcgbGlua3Mgb24gZW50aXJlIGNocm9tb3NvbWUsIAogICAgICAgYnV0IHJlc3RyaWN0ZWQgdG8gKy8tMTAwa2IgZ2VuZSB3aW5kb3cgYXJvdW5kIFRTUyIpCmBgYAoKYGBge3IsIGZpZy53aWR0aCA9IDgsIGZpZy5oZWlnaHQ9OH0KY29ycmVsYXRpb25zX2dlbmVfd2luZG93X3N1YiA8LSBjb3JyZWxhdGlvbnNfZ2VuZV93aW5kb3dbbmFtZXMoY29ycmVsYXRpb25zXzI1MGtiKV0KCmdncGxvdCgpICsgI2dlb21fZGVuc2l0eTJkX2ZpbGxlZChhZXMoeCA9IGNvcnJlbGF0aW9uc18yNTBrYiwgeSA9IGNvcnJzWzFdKSkgIysKICBnZW9tX3BvaW50KGFlcyh4ID0gY29ycmVsYXRpb25zXzI1MGtiLCB5ID0gY29ycmVsYXRpb25zX2dlbmVfd2luZG93X3N1YikpCmBgYAoKIyBBZGFwdGVkIEFyY2hyIEdlbmUgQWN0aXZpdHkgU2NvcmUgZnVuY3Rpb24KCiMjIEFyY2hSIEdlbmUgQWN0aXZpdHkgU2NvcmVzIHVzaW5nIGdlbmUgYm9keQoKPGRldGFpbHM+CjxzdW1tYXJ5PkFyY2hSIEdlbmUgQWN0aXZpdHkgU2NvcmVzIHVzaW5nIGdlbmUgYm9keTwvc3VtbWFyeT4KCmBgYCN7cn0KI3NhdmVBcmNoUlByb2plY3QocHJvaiwgIjEyX0NvcHkyLyIpCgpwcm9qIDwtIGxvYWRBcmNoUlByb2plY3QoIjEyX0NvcHkyLyIpCgpwcm9qIDwtIGFkZEthdGhpR2VuZVNjb3JlTWF0cml4KAogIHByb2osCiAgZ2VuZXMgPSBnZXRHZW5lcyhwcm9qKSwKICBwZWFrcyA9IGdldFBlYWtTZXQocHJvaiksCiAgZ2VuZU1vZGVsID0gImV4cCgtYWJzKHgpLzUwMDApICsgZXhwKC0xKSIsCiAgbWF0cml4TmFtZSA9ICJHZW5lU2NvcmVNYXRyaXgiLAogIGV4dGVuZFVwc3RyZWFtID0gYygxMDAwLCAxMDAwMDApLAogIGV4dGVuZERvd25zdHJlYW0gPSBjKDEwMDAsIDEwMDAwMCksCiAgI2dlbmVVcHN0cmVhbSA9IDUwMDAsICNOZXcgUGFyYW0KICAjZ2VuZURvd25zdHJlYW0gPSAwLCAjTmV3IFBhcmFtCiAgdXNlR2VuZUJvdW5kYXJpZXMgPSBUUlVFLAogIHVzZVRTUyA9IEZBTFNFLCAjTmV3IFBhcmFtCiAgZXh0ZW5kVFNTID0gRkFMU0UsCiAgdGlsZVNpemUgPSA1MDAsCiAgY2VpbGluZyA9IDQsCiAgZ2VuZVNjYWxlRmFjdG9yID0gNSwgI05ldyBQYXJhbQogIHNjYWxlVG8gPSAxMDAwMCwKICBleGNsdWRlQ2hyID0gYygiY2hyWSIsICJjaHJNIiksCiAgYmxhY2tsaXN0ID0gZ2V0QmxhY2tsaXN0KHByb2opLAogIHRocmVhZHMgPSAxLAogIHBhcmFsbGVsUGFyYW0gPSBOVUxMLAogIHN1YlRocmVhZGluZyA9IFRSVUUsCiAgZm9yY2UgPSBUUlVFLAogIGxvZ0ZpbGUgPSBjcmVhdGVMb2dGaWxlKCIuYWRkS2F0aGlHZW5lU2NvcmVNYXQiKSkKCgpzY29yZXMgPC0gZ2V0TWF0cml4RnJvbVByb2plY3QocHJvaiwgdXNlTWF0cml4ID0gIkdlbmVTY29yZU1hdHJpeCIpCgpzY29yZXNfbWF0IDwtIGFzc2F5cyhzY29yZXMpW1sxXV0Kcm93bmFtZXMoc2NvcmVzX21hdCkgPC0gcm93RGF0YShzY29yZXMpJG5hbWUKCgojIHNjZSA8LSBTaW5nbGVDZWxsRXhwZXJpbWVudChsaXN0KHNjb3Jlcz1zY29yZXNfbWF0KSwKIyAgICAgICAgICAgICAgICAgICAgICAgICAgIHJvd0RhdGEgPSBhcy5kYXRhLmZyYW1lKHJvd0RhdGEoc2NvcmVzKSksCiMgICAgICAgICAgICAgICAgICAgICAgICAgICBjb2xEYXRhID0gYXMuZGF0YS5mcmFtZShjb2xuYW1lcyhzY29yZXNfbWF0KSkpCiMgCiMgd3JpdGVINUFEKHNjZSwgIi9vbWljcy9ncm91cHMvT0UwNTMzL2ludGVybmFsL2thdGhhcmluYS9zY0RvUkkvZ2FzdHJ1bGF0aW9uX2RhdGEvanVweXRlcl9ub3RlYm9va3MvcDJnX2dlbmVfYWN0aXZpdHlfc2NvcmVzL2FyY2hyX3Njb3Jlc19nZW5lX2JvZHlfcGVha19iYXNlZCIsIFhfbmFtZSA9ICJzY29yZXMiKQoKYGBgCjwvZGV0YWlscz4KCkNvcnJlbGF0aW5nIGdlbmUgZXhwcmVzc2lvbiB3aXRoIGFjdGl2aXR5IHNjb3JlczoKCmBgYCN7cn0KYXJjaHJfZ2VuZV9ib2R5X2FnZyA8LSBrbm5fYWdncmVnYXRlcyhzY29yZXNfbWF0LCBjZWxsX2FnZ19saXN0KQoKZ2VuZV9ib2R5X2tubiA8LSByb3d3aXNlX2NvcnJlbGF0aW9ucyhybmFfYWdnLCBhcmNocl9nZW5lX2JvZHlfYWdnLCAiQXJjaFIgZ2VuZSBhY3Rpdml0eSBzY29yZXMgYmFzZWQgb24gcGVhayBtYXRyaXgsIHVzaW5nIGdlbmUgYm9keSIpCgoKY293cGxvdDo6cGxvdF9ncmlkKGFyY2hyX2tubltbMl1dLCBnZW5lX2JvZHlfa25uW1syXV0sIG5jb2wgPSAyKQoKcDEgPC0gZ2dwbG90KCkgKyBnZW9tX2RlbnNpdHlfMmRfZmlsbGVkKGFlcyh4ID0gZ2VuZV9ib2R5X2tubltbMV1dLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5ID0gYXJjaHJfa25uW1sxXV0pLCBhbHBoYSA9IC41KSArCiAgZ2VvbV9wb2ludChhZXMoeCA9IGdlbmVfYm9keV9rbm5bWzFdXSwgeSA9IGFyY2hyX2tubltbMV1dKSkgKwogIGdlb21fbGluZShhZXMoeCA9IGdlbmVfYm9keV9rbm5bWzFdXSwgeSA9IGdlbmVfYm9keV9rbm5bWzFdXSksIGNvbCA9ICJyZWQiKSArCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIk5vbmUiKSAKYGBgCgoKIyMgQXJjaFIgR2VuZSBBY3Rpdml0eSBTY29yZXMgdXNpbmcgVFNTLCBubyBnZW5lIGJvZHkKCjxkZXRhaWxzPgo8c3VtbWFyeT5BcmNoUiBHZW5lIEFjdGl2aXR5IFNjb3JlcyB1c2luZyBUU1MsIG5vIGdlbmUgYm9keTwvc3VtbWFyeT4KCgpgYGAje3J9CiNzYXZlQXJjaFJQcm9qZWN0KHByb2osICIxMl9Db3B5MS8iKQoKcHJvaiA8LSBsb2FkQXJjaFJQcm9qZWN0KCIxMl8iKQoKcHJvaiA8LSBhZGRHZW5lU2NvcmVNYXRyaXgoCiAgcHJvaiwKICBnZW5lcyA9IGdldEdlbmVzKHByb2opLAogIGdlbmVNb2RlbCA9ICJleHAoLWFicyh4KS81MDAwKSIsCiAgbWF0cml4TmFtZSA9ICJHZW5lU2NvcmVNYXRyaXgiLAogIGV4dGVuZFVwc3RyZWFtID0gYygxMDAwLCAxMDAwMDApLAogIGV4dGVuZERvd25zdHJlYW0gPSBjKDEwMDAsIDEwMDAwMCksCiAgI2dlbmVVcHN0cmVhbSA9IDUwMDAsICNOZXcgUGFyYW0KICAjZ2VuZURvd25zdHJlYW0gPSAwLCAjTmV3IFBhcmFtCiAgdXNlR2VuZUJvdW5kYXJpZXMgPSBUUlVFLAogIHVzZVRTUyA9IFRSVUUsICNOZXcgUGFyYW0KICBleHRlbmRUU1MgPSBGQUxTRSwKICB0aWxlU2l6ZSA9IDUwMCwKICBjZWlsaW5nID0gNCwKICBnZW5lU2NhbGVGYWN0b3IgPSA1LCAjTmV3IFBhcmFtCiAgc2NhbGVUbyA9IDEwMDAwLAogIGV4Y2x1ZGVDaHIgPSBjKCJjaHJZIiwgImNock0iKSwKICBibGFja2xpc3QgPSBnZXRCbGFja2xpc3QocHJvaiksCiAgdGhyZWFkcyA9IDEsCiAgcGFyYWxsZWxQYXJhbSA9IE5VTEwsCiAgc3ViVGhyZWFkaW5nID0gVFJVRSwKICBmb3JjZSA9IFRSVUUsCiAgbG9nRmlsZSA9IGNyZWF0ZUxvZ0ZpbGUoIi5hZGRHZW5lU2NvcmVNYXRyaXgiKSkKCgpzY29yZXMgPC0gZ2V0TWF0cml4RnJvbVByb2plY3QocHJvaiwgdXNlTWF0cml4ID0gIkdlbmVTY29yZU1hdHJpeCIpCgpzY29yZXNfbWF0IDwtIGFzc2F5cyhzY29yZXMpW1sxXV0Kcm93bmFtZXMoc2NvcmVzX21hdCkgPC0gcm93RGF0YShzY29yZXMpJG5hbWUKCgojIHNjZSA8LSBTaW5nbGVDZWxsRXhwZXJpbWVudChsaXN0KHNjb3Jlcz1zY29yZXNfbWF0KSwKIyAgICAgICAgICAgICAgICAgICAgICAgICAgIHJvd0RhdGEgPSBhcy5kYXRhLmZyYW1lKHJvd0RhdGEoc2NvcmVzKSksCiMgICAgICAgICAgICAgICAgICAgICAgICAgICBjb2xEYXRhID0gYXMuZGF0YS5mcmFtZShjb2xuYW1lcyhzY29yZXNfbWF0KSkpCiMgCiMgd3JpdGVINUFEKHNjZSwgIi9vbWljcy9ncm91cHMvT0UwNTMzL2ludGVybmFsL2thdGhhcmluYS9zY0RvUkkvZ2FzdHJ1bGF0aW9uX2RhdGEvanVweXRlcl9ub3RlYm9va3MvcDJnX2dlbmVfYWN0aXZpdHlfc2NvcmVzL2FyY2hyX3Njb3Jlc190c3MiLCBYX25hbWUgPSAic2NvcmVzIikKCmBgYAoKIyMgQXJjaFIgZ2VuZSBhY3Rpdml0eSBzY29yZXMgY29tcHV0ZWQgdXNpbmcgVFNTLCBubyBnZW5lIGJvZHkgYW5kIFBlYWtNYXRyaXggaW5zdGVhZCBvZiBUaWxlTWF0cml4Cgo8ZGV0YWlscz4KPHN1bW1hcnk+QXJjaFIgZ2VuZSBhY3Rpdml0eSBzY29yZXMgY29tcHV0ZWQgdXNpbmcgVFNTLCBubyBnZW5lIGJvZHkgYW5kIFBlYWtNYXRyaXggaW5zdGVhZCBvZiBUaWxlTWF0cml4PC9zdW1tYXJ5PgoKYGBgI3tyfQpwcm9qIDwtIGxvYWRBcmNoUlByb2plY3QoIjEyX0NvcHkvIikKCnByb2ogPC0gYWRkS2F0aGlHZW5lU2NvcmVNYXRyaXgoCiAgcHJvaiwKICBnZW5lcyA9IGdldEdlbmVzKHByb2opLAogIHBlYWtzID0gZ2V0UGVha1NldChwcm9qKSwKICBnZW5lTW9kZWwgPSAiZXhwKC1hYnMoeCkvNTAwMCkiLAogIG1hdHJpeE5hbWUgPSAiR2VuZVNjb3JlTWF0cml4IiwKICBleHRlbmRVcHN0cmVhbSA9IGMoMTAwMCwgMTAwMDAwKSwKICBleHRlbmREb3duc3RyZWFtID0gYygxMDAwLCAxMDAwMDApLAogICNnZW5lVXBzdHJlYW0gPSA1MDAwLCAjTmV3IFBhcmFtCiAgI2dlbmVEb3duc3RyZWFtID0gMCwgI05ldyBQYXJhbQogIHVzZUdlbmVCb3VuZGFyaWVzID0gVFJVRSwKICB1c2VUU1MgPSBUUlVFLCAjTmV3IFBhcmFtCiAgZXh0ZW5kVFNTID0gRkFMU0UsCiAgdGlsZVNpemUgPSA1MDAsCiAgY2VpbGluZyA9IDQsCiAgZ2VuZVNjYWxlRmFjdG9yID0gNSwgI05ldyBQYXJhbQogIHNjYWxlVG8gPSAxMDAwMCwKICBleGNsdWRlQ2hyID0gYygiY2hyWSIsICJjaHJNIiksCiAgYmxhY2tsaXN0ID0gZ2V0QmxhY2tsaXN0KHByb2opLAogIHRocmVhZHMgPSAxLAogIHBhcmFsbGVsUGFyYW0gPSBOVUxMLAogIHN1YlRocmVhZGluZyA9IFRSVUUsCiAgZm9yY2UgPSBUUlVFLAogIGxvZ0ZpbGUgPSBjcmVhdGVMb2dGaWxlKCIuYWRkS2F0aGlHZW5lU2NvcmVNYXQiKSkKCnNjb3JlcyA8LSBnZXRNYXRyaXhGcm9tUHJvamVjdChwcm9qLCB1c2VNYXRyaXggPSAiR2VuZVNjb3JlTWF0cml4IikKCnNjb3Jlc19tYXQgPC0gYXNzYXlzKHNjb3JlcylbWzFdXQpyb3duYW1lcyhzY29yZXNfbWF0KSA8LSByb3dEYXRhKHNjb3JlcykkbmFtZQoKIwojIHNjZSA8LSBTaW5nbGVDZWxsRXhwZXJpbWVudChsaXN0KHNjb3Jlcz1zY29yZXNfbWF0KSwKIyAgICAgICAgICAgICAgICAgICAgICAgICAgIHJvd0RhdGEgPSBhcy5kYXRhLmZyYW1lKHJvd25hbWVzKHNjb3Jlc19tYXQpKSwKIyAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbERhdGEgPSBhcy5kYXRhLmZyYW1lKGNvbG5hbWVzKHNjb3Jlc19tYXQpKSkKIyAKIyB3cml0ZUg1QUQoc2NlLCAiL29taWNzL2dyb3Vwcy9PRTA1MzMvaW50ZXJuYWwva2F0aGFyaW5hL3NjRG9SSS9nYXN0cnVsYXRpb25fZGF0YS9qdXB5dGVyX25vdGVib29rcy9wMmdfZ2VuZV9hY3Rpdml0eV9zY29yZXMvYXJjaHJfc2NvcmVzX3BlYWtfYmFzZWQiLCBYX25hbWUgPSAic2NvcmVzIikKYGBgCgpgYGAje3J9CgoKCiMgc2NlIDwtIFNpbmdsZUNlbGxFeHBlcmltZW50KGxpc3QocDJnX21hdCA9IHAyZ19tYXQpKQojIAojIHdyaXRlSDVBRChzY2UsICIvb21pY3MvZ3JvdXBzL09FMDUzMy9pbnRlcm5hbC9rYXRoYXJpbmEvc2NEb1JJL2dhc3RydWxhdGlvbl9kYXRhL2p1cHl0ZXJfbm90ZWJvb2tzL3AyZ19nZW5lX2FjdGl2aXR5X3Njb3Jlcy9wMmdfbWF0XzI1MGtiIiwKIyAgICAgICAgICAgWF9uYW1lID0gInAyZ19tYXQiKQoKIyAKIyAKIyBzY2UgPC0gU2luZ2xlQ2VsbEV4cGVyaW1lbnQobGlzdChwZWFrX21hdCA9IHBlYWtfbWF0KSkKIyAKIyB3cml0ZUg1QUQoc2NlLCAiL29taWNzL2dyb3Vwcy9PRTA1MzMvaW50ZXJuYWwva2F0aGFyaW5hL3NjRG9SSS9nYXN0cnVsYXRpb25fZGF0YS9qdXB5dGVyX25vdGVib29rcy9wMmdfZ2VuZV9hY3Rpdml0eV9zY29yZXMvcGVha19tYXQiLAojICAgICAgICAgICBYX25hbWUgPSAicGVha19tYXQiKQoKCiMgY3BfbmFtZXMgPC0gY29sbmFtZXMoY29sRGF0YShnZW5lX2V4cHIpKQojIGNwX25hbWVzWzIwXSA8LSAiY2VsbHR5cGVzIgojIGNvbG5hbWVzKGNvbERhdGEoZ2VuZV9leHByKSkgPC0gY3BfbmFtZXMKCnNjZSA8LSBTaW5nbGVDZWxsRXhwZXJpbWVudChsaXN0KGdlbmVzID0gZXhwcl9tYXQpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAjcm93RGF0YSA9IGFzLmRhdGEuZnJhbWUocm93bmFtZXMoZ2VuZV9leHByKSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbERhdGEgPSBhcy5kYXRhLmZyYW1lKGNvbERhdGEoZ2VuZV9leHByKSkpCgojIHdyaXRlSDVBRChzY2UsICIvb21pY3MvZ3JvdXBzL09FMDUzMy9pbnRlcm5hbC9rYXRoYXJpbmEvc2NEb1JJL2dhc3RydWxhdGlvbl9kYXRhL2p1cHl0ZXJfbm90ZWJvb2tzL3AyZ19nZW5lX2FjdGl2aXR5X3Njb3Jlcy9nZW5lX2V4cHJfbWF0IiwKIyAgICAgICAgICAgWF9uYW1lID0gImdlbmVzIikKIyAKIyAKIyAjcDJnX21hdF9ub3JtIDwtIHAyZ19tYXQgLyByb3dTdW1zKHAyZ19tYXQpCiMgc2NvcmVzIDwtIHAyZ19tYXQgJSolIHBlYWtfbWF0CiMgc2NvcmVzIDwtIHQodChzY29yZXMpIC8gY29sU3VtcyhzY29yZXMpKQojIHN0b3BpZm5vdChhbnkoaXMubmEoc2NvcmVzKSkgPT0gRkFMU0UpCiMgc2NvcmVzQHggPC0gcG1pbigxZTksIGV4cChzY29yZXNAeCkgLSAxKQojIAojIAojIAojIHNjZSA8LSBTaW5nbGVDZWxsRXhwZXJpbWVudChsaXN0KGludmVzdGlnYXRpb24gPSBpbnZlc3RpZ2F0aW9uKSkKIyAKIyB3cml0ZUg1QUQoc2NlLCAiL29taWNzL2dyb3Vwcy9PRTA1MzMvaW50ZXJuYWwva2F0aGFyaW5hL3NjRG9SSS9nYXN0cnVsYXRpb25fZGF0YS9qdXB5dGVyX25vdGVib29rcy9wMmdfZ2VuZV9hY3Rpdml0eV9zY29yZXMvaW52ZXN0aWdhdGlvbl9zY29yZXMiLAojICAgICAgICAgICBYX25hbWUgPSAiaW52ZXN0aWdhdGlvbiIpCgoKCgoKIyBsYXRlbnQgZW1iZWRkaW5nCmVtYiA8LSBnZXRSZWR1Y2VkRGltcygKICBBcmNoUlByb2ogPSBwcm9qLAogIHJlZHVjZWREaW1zID0gImF0YWNfTFNJXzEwMDAwMCIsCiAgcmV0dXJuTWF0cml4ID0gVFJVRSwKICBkaW1zVG9Vc2UgPSAxOjMwLAogIHNjYWxlRGltcyA9IE5VTEwsCiAgY29yQ3V0T2ZmID0gMC43NQopCmRpbShlbWIpCgoKc2NlIDwtIFNpbmdsZUNlbGxFeHBlcmltZW50KGxpc3QoZW1iZWRkaW5nID0gZW1iKSkKCndyaXRlSDVBRChzY2UsICIvb21pY3MvZ3JvdXBzL09FMDUzMy9pbnRlcm5hbC9rYXRoYXJpbmEvc2NEb1JJL2dhc3RydWxhdGlvbl9kYXRhL2p1cHl0ZXJfbm90ZWJvb2tzL3AyZ19nZW5lX2FjdGl2aXR5X3Njb3Jlcy9hcmNocl9sc2lfZW1iZWRkaW5nIiwKICAgICAgICAgIFhfbmFtZSA9ICJlbWJlZGRpbmciKQoKCmBgYA==